{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 0、生成数据\n",
    "- 简单序列数据形如：`a a a a b b b b EOS, a a b b EOS, a a a a a b b b b b EOS`\n",
    "    - EOS:end of sequence; UNK:unkown\n",
    "- 给定序列 $\\{t_1,t_2...t_{n-1}\\}$，预测 $t_n$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "np.random.seed(42)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_dataset(num_sequences=100):\n",
    "    samples = []\n",
    "    \n",
    "    for _ in range(num_sequences):\n",
    "        num_tokens = np.random.randint(1, 10)\n",
    "        sample = ['a']*num_tokens + ['b']*num_tokens + ['EOS']\n",
    "        samples.append(sample)\n",
    "    return samples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "生成数据示例：\n",
      "['a', 'a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'EOS']\n"
     ]
    }
   ],
   "source": [
    "sequences = generate_dataset()\n",
    "\n",
    "print('生成数据示例：')\n",
    "print(sequences[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### tokens --> indices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We have 100 sentences and 4 unique tokens in our dataset (including UNK).\n",
      "\n",
      "The index of 'b' is 1\n",
      "The word corresponding to index 1 is 'b'\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def sequences_to_dicts(sequences):\n",
    "    flatten = lambda l:[item for sublist in l for item in sublist]\n",
    "    all_words = flatten(sequences)\n",
    "    \n",
    "    word_count = defaultdict(int)\n",
    "    for word in all_words:\n",
    "        word_count[word] += 1\n",
    "    \n",
    "    word_count = sorted(list(word_count.items()), key=lambda l:-l[1])\n",
    "    \n",
    "    unique_words = [item[0] for item in word_count]\n",
    "    unique_words.append('UNK')\n",
    "    \n",
    "    num_sentences, vocab_size = len(sequences), len(unique_words)\n",
    "    word_to_idx = defaultdict(lambda: vocab_size-1)\n",
    "    idx_to_word = defaultdict(lambda: 'UNK')\n",
    "    for idx, word in enumerate(unique_words):\n",
    "        word_to_idx[word] = idx\n",
    "        idx_to_word[idx] = word\n",
    "\n",
    "    return word_to_idx, idx_to_word, num_sentences, vocab_size\n",
    "    \n",
    "word_to_idx, idx_to_word, num_sequences, vocab_size = sequences_to_dicts(sequences)\n",
    "\n",
    "print(f'We have {num_sequences} sentences and {len(word_to_idx)} unique tokens in our dataset (including UNK).\\n')\n",
    "print('The index of \\'b\\' is', word_to_idx['b'])\n",
    "print(f'The word corresponding to index 1 is \\'{idx_to_word[1]}\\'')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 训练、验证、测试集及数据生成器"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We have 80 samples in the training set.\n",
      "We have 10 samples in the validation set.\n",
      "We have 10 samples in the test set.\n"
     ]
    }
   ],
   "source": [
    "from torch.utils import data\n",
    "\n",
    "class Dataset(data.Dataset):\n",
    "    def __init__(self, inputs, targets):\n",
    "        self.inputs = inputs\n",
    "        self.targets = targets\n",
    "    def __len__(self):\n",
    "        return len(self.targets)\n",
    "    def __getitem__(self, index):\n",
    "        X = self.inputs[index]\n",
    "        y = self.targets[index]\n",
    "        return X, y\n",
    "    \n",
    "def create_datasets(sequences, dataset_class, p_train=0.8, p_val=0.1, p_test=0.1):\n",
    "    num_train = int(len(sequences)*p_train)\n",
    "    num_val = int(len(sequences)*p_val)    \n",
    "    num_test = int(len(sequences)*p_test)    \n",
    "    \n",
    "    sequences_train = sequences[:num_train]\n",
    "    sequences_val = sequences[num_train: num_train+num_val]\n",
    "    sequences_test = sequences[-num_test:]\n",
    "    \n",
    "    def get_inputs_targets_from_sequences(sequences):\n",
    "        inputs, targets = [], []\n",
    "        for sequence in sequences:\n",
    "            inputs.append(sequence[:-1])\n",
    "            targets.append(sequence[1:])\n",
    "        return inputs, targets\n",
    "    \n",
    "    inputs_train, targets_train = get_inputs_targets_from_sequences(sequences_train)\n",
    "    inputs_val, targets_val = get_inputs_targets_from_sequences(sequences_val)\n",
    "    inputs_test, targets_test = get_inputs_targets_from_sequences(sequences_test)\n",
    "    \n",
    "    training_set = dataset_class(inputs_train, targets_train)\n",
    "    validation_set = dataset_class(inputs_val, targets_val)\n",
    "    test_set = dataset_class(inputs_test, targets_test)\n",
    "\n",
    "    return training_set, validation_set, test_set\n",
    "\n",
    "training_set, validation_set, test_set = create_datasets(sequences, Dataset)\n",
    "\n",
    "print(f'We have {len(training_set)} samples in the training set.')\n",
    "print(f'We have {len(validation_set)} samples in the validation set.')\n",
    "print(f'We have {len(test_set)} samples in the test set.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### One-hot encodings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Our one-hot encoding of 'a' has shape (4,).\n",
      "Our one-hot encoding of 'a b' has shape (2, 4, 1).\n"
     ]
    }
   ],
   "source": [
    "def one_hot_encode(idx, vocab_size):\n",
    "    one_hot = np.zeros(vocab_size)\n",
    "    one_hot[idx] = 1\n",
    "    return one_hot\n",
    "\n",
    "def one_hot_encode_sequence(sequence, vocab_size):\n",
    "    encoding = np.array(\n",
    "        [one_hot_encode(word_to_idx[word], vocab_size) for word in sequence])\n",
    "    encoding = encoding.reshape(encoding.shape[0], encoding.shape[1], 1)\n",
    "    \n",
    "    return encoding\n",
    "\n",
    "test_word = one_hot_encode(word_to_idx['a'], vocab_size)\n",
    "print(f'Our one-hot encoding of \\'a\\' has shape {test_word.shape}.')\n",
    "\n",
    "test_sentence = one_hot_encode_sequence(['a', 'b'], vocab_size)\n",
    "print(f'Our one-hot encoding of \\'a b\\' has shape {test_sentence.shape}.')\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1、RNN\n",
    "\n",
    "- $x$ is the input sequence of samples,\n",
    "- $U$ is a weight matrix applied to the given input sample,\n",
    "- $V$ is a weight matrix used for the recurrent computation in order to pass memory along the sequence,\n",
    "- $W$ is a weight matrix used to compute the output of the every timestep (given that every timestep requires an output),\n",
    "- $h$ is the hidden state (the network's memory) for a given time step, and\n",
    "- $o$ is the resulting output.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 权重系数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "hidden_size = 50\n",
    "vocab_size = len(word_to_idx)\n",
    "\n",
    "def init_orthogonal(param):\n",
    "    # 权重矩阵初始化为正交\n",
    "    if param.ndim < 2:\n",
    "        raise ValueError(\"Only parameters with 2 or more dimensions are supported.\")\n",
    "    rows, cols = param.shape\n",
    "    \n",
    "    new_param = np.random.randn(rows, cols)\n",
    "    if rows < cols:\n",
    "        new_param = new_param.T\n",
    "    \n",
    "    # Compute QR factorization\n",
    "    # todo:待理解\n",
    "    q, r = np.linalg.qr(new_param)\n",
    "    d = np.diag(r, 0)\n",
    "    ph = np.sign(d)\n",
    "    q *= ph\n",
    "    \n",
    "    if rows < cols:\n",
    "        q = q.T\n",
    "    new_param = q\n",
    "    \n",
    "    return new_param"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def init_rnn(hidden_size, vocab_size):\n",
    "    # 初始化所有权重系数\n",
    "    U = np.zeros((hidden_size, vocab_size))\n",
    "    V = np.zeros((hidden_size, hidden_size))\n",
    "    W = np.zeros((vocab_size, hidden_size))\n",
    "    \n",
    "    b_hidden = np.zeros((hidden_size, 1))\n",
    "    b_out = np.zeros((vocab_size, 1))\n",
    "\n",
    "    U = init_orthogonal(U)\n",
    "    V = init_orthogonal(V)\n",
    "    W = init_orthogonal(W)\n",
    "\n",
    "    return U, V, W, b_hidden, b_out\n",
    "\n",
    "params = init_rnn(hidden_size=hidden_size, vocab_size=vocab_size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 激活函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sigmoid(x, derivative=False):\n",
    "    x_safe = x + 1e-12\n",
    "    f = 1 / (1 + np.exp(-x_safe))\n",
    "    \n",
    "    if derivative: \n",
    "        return f * (1 - f)\n",
    "    else: \n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tanh(x, derivative=False):\n",
    "    x_safe = x + 1e-12\n",
    "    f = (np.exp(x_safe)-np.exp(-x_safe))/(np.exp(x_safe)+np.exp(-x_safe))\n",
    "    \n",
    "    if derivative: \n",
    "        return 1-f**2\n",
    "    else: \n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def softmax(x, derivative=False):\n",
    "\n",
    "    x_safe = x + 1e-12\n",
    "    f = np.exp(x_safe) / np.sum(np.exp(x_safe))\n",
    "    \n",
    "    if derivative: # Return the derivative of the function evaluated at x\n",
    "        pass # We will not need this one\n",
    "    else: \n",
    "        return f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 前向传播"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def forward_pass(inputs, hidden_state, params):\n",
    "    U, V, W, b_hidden, b_out = params\n",
    "\n",
    "    outputs, hidden_states = [], []\n",
    "    \n",
    "    for t in range(len(inputs)):\n",
    "        hidden_state = tanh(np.dot(U, inputs[t]) + np.dot(V, hidden_state) \n",
    "                            + b_hidden)\n",
    "        out = softmax(np.dot(W, hidden_state) + b_out)\n",
    "        \n",
    "        outputs.append(out)\n",
    "        hidden_states.append(hidden_state.copy())\n",
    "    \n",
    "    return outputs, hidden_states"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input sequence:\n",
      "['a', 'a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b']\n",
      "\n",
      "Target sequence:\n",
      "['a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'EOS']\n",
      "\n",
      "Predicted sequence:\n",
      "['UNK', 'UNK', 'UNK', 'b', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'EOS', 'EOS', 'b']\n"
     ]
    }
   ],
   "source": [
    "test_input_sequence, test_target_sequence = training_set[0]\n",
    "\n",
    "test_input = one_hot_encode_sequence(test_input_sequence, vocab_size)\n",
    "test_target = one_hot_encode_sequence(test_target_sequence, vocab_size)\n",
    "\n",
    "hidden_state = np.zeros((hidden_size, 1))\n",
    "\n",
    "outputs, hidden_states = forward_pass(test_input, hidden_state, params)\n",
    "\n",
    "print('Input sequence:')\n",
    "print(test_input_sequence)\n",
    "\n",
    "print('\\nTarget sequence:')\n",
    "print(test_target_sequence)\n",
    "\n",
    "print('\\nPredicted sequence:')\n",
    "print([idx_to_word[np.argmax(output)] for output in outputs])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 反向传播"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def clip_gradient_norm(grads, max_norm=0.25):\n",
    "    \"\"\"\n",
    "    Clips gradients to have a maximum norm of `max_norm`.\n",
    "    This is to prevent the exploding gradients problem.\n",
    "    \"\"\" \n",
    "    max_norm = float(max_norm)\n",
    "    total_norm = 0\n",
    "    \n",
    "    for grad in grads:\n",
    "        grad_norm = np.sum(np.power(grad, 2))\n",
    "        total_norm += grad_norm\n",
    "    \n",
    "    total_norm = np.sqrt(total_norm)\n",
    "    \n",
    "    clip_coef = max_norm / (total_norm + 1e-6)\n",
    "    \n",
    "    if clip_coef < 1:\n",
    "        for grad in grads:\n",
    "            grad *= clip_coef\n",
    "    \n",
    "    return grads"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We get a loss of:\n",
      "4.553408581307239\n"
     ]
    }
   ],
   "source": [
    "# todo: 细节待理解\n",
    "def backward_pass(inputs, outputs, hidden_states, targets, params):\n",
    "    \"\"\"\n",
    "    Computes the backward pass of a vanilla RNN.\n",
    "    \n",
    "    Args:\n",
    "     `inputs`: sequence of inputs to be processed\n",
    "     `outputs`: sequence of outputs from the forward pass\n",
    "     `hidden_states`: sequence of hidden_states from the forward pass\n",
    "     `targets`: sequence of targets\n",
    "     `params`: the parameters of the RNN\n",
    "    \"\"\"\n",
    "    U, V, W, b_hidden, b_out = params\n",
    "    \n",
    "    d_U, d_V, d_W = np.zeros_like(U), np.zeros_like(V), np.zeros_like(W)\n",
    "    d_b_hidden, d_b_out = np.zeros_like(b_hidden), np.zeros_like(b_out)\n",
    "    \n",
    "    # Keep track of hidden state derivative and loss\n",
    "    d_h_next = np.zeros_like(hidden_states[0])\n",
    "    loss = 0\n",
    "    \n",
    "    # For each element in output sequence\n",
    "    # NB: We iterate backwards s.t. t = N, N-1, ... 1, 0\n",
    "    for t in reversed(range(len(outputs))):\n",
    "\n",
    "        # Compute cross-entropy loss (as a scalar)\n",
    "        loss += -np.mean(np.log(outputs[t]+1e-12) * targets[t])\n",
    "        \n",
    "        # Backpropagate into output (derivative of cross-entropy)\n",
    "        # if you're confused about this step, see this link for an explanation:\n",
    "        # http://cs231n.github.io/neural-networks-case-study/#grad\n",
    "        d_o = outputs[t].copy()\n",
    "        d_o[np.argmax(targets[t])] -= 1\n",
    "        \n",
    "        # Backpropagate into W\n",
    "        d_W += np.dot(d_o, hidden_states[t].T)\n",
    "        d_b_out += d_o\n",
    "        \n",
    "        # Backpropagate into h\n",
    "        d_h = np.dot(W.T, d_o) + d_h_next\n",
    "        \n",
    "        # Backpropagate through non-linearity\n",
    "        d_f = tanh(hidden_states[t], derivative=True) * d_h\n",
    "        d_b_hidden += d_f\n",
    "        \n",
    "        # Backpropagate into U\n",
    "        d_U += np.dot(d_f, inputs[t].T)\n",
    "        \n",
    "        # Backpropagate into V\n",
    "        d_V += np.dot(d_f, hidden_states[t-1].T)\n",
    "        d_h_next = np.dot(V.T, d_f)\n",
    "    \n",
    "    # Pack gradients\n",
    "    grads = d_U, d_V, d_W, d_b_hidden, d_b_out    \n",
    "    \n",
    "    # Clip gradients\n",
    "    grads = clip_gradient_norm(grads)\n",
    "    \n",
    "    return loss, grads\n",
    "\n",
    "\n",
    "loss, grads = backward_pass(test_input, outputs, hidden_states, test_target, params)\n",
    "\n",
    "print('We get a loss of:')\n",
    "print(loss)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 训练模型"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def update_parameters(params, grads, lr=1e-3):\n",
    "    for param, grad in zip(params, grads):\n",
    "        param -= lr * grad\n",
    "    \n",
    "    return params"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epoch 0, training loss: 3.703043404000114, validation loss: 3.7253638510366778\n",
      "Epoch 100, training loss: 2.5482632393055744, validation loss: 2.5655720230034285\n",
      "Epoch 200, training loss: 1.9880142333179642, validation loss: 2.0131189666321054\n",
      "Epoch 300, training loss: 1.7188008978786447, validation loss: 1.7539022584112005\n",
      "Epoch 400, training loss: 1.5879113487879617, validation loss: 1.6303629072567305\n",
      "Epoch 500, training loss: 1.5075009671922137, validation loss: 1.5533692674689297\n",
      "Epoch 600, training loss: 1.4474347963188197, validation loss: 1.4937265958119625\n",
      "Epoch 700, training loss: 1.3952514236497051, validation loss: 1.4396767069478489\n",
      "Epoch 800, training loss: 1.3423156600350297, validation loss: 1.383039185570785\n",
      "Epoch 900, training loss: 1.2773975256533352, validation loss: 1.3135134700978988\n",
      "Input sentence:\n",
      "['a', 'a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b']\n",
      "\n",
      "Target sequence:\n",
      "['a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'EOS']\n",
      "\n",
      "Predicted sequence:\n",
      "['a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'EOS']\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX8AAAECCAYAAAAW+Nd4AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nO3deXxU1f3/8ddJAiSyQ1AQBAQKgSCIkLAqOwRFRQR3FK2g1KW2FaXa/qS2WNDaYqn7ivvSCl9AFlnVCBFZBNl3EFSEIKsQCDm/P06GbBNIwkxuZub9fDzuY27unLnzuYF8zr3n3HOusdYiIiKRJcrrAEREpPQp+YuIRCAlfxGRCKTkLyISgZT8RUQiUIzXARRFfHy8bdiwoddhiIiElKVLl+611tby915IJP+GDRuyZMkSr8MQEQkpxpjthb2nZh8RkQik5C8iEoGU/EVEIlBItPmLSOk4ceIEO3fu5NixY16HIsUQGxtLvXr1KFeuXJE/o+QvIqfs3LmTypUr07BhQ4wxXocjRWCtJT09nZ07d3LhhRcW+XNq9hGRU44dO0bNmjWV+EOIMYaaNWsW+2pNyV9E8lDiDz0l+TcL6+S/ahX8/vdw9KjXkYiIlC1hnfy3b4d//QsWLvQ6EhEpin//+9906dKFuLg4unTpwscff1yszy9fvpzXXnvtjOV+/PFHnnjiiZKG6Ve3bt0Cur9gC+sO38sy5xHDpcyZcoKePc/xOhwROYP777+f+++/nyZNmpCamlrsz7dp04Y2bdqcsVzt2rV55JFHShJi2Ajr5F/53Dg6sog501ry92eU/EWK5YEH4JtvArvPiy+G8eOL9ZFt27bx6KOPEhcXR1ZWFq+99hqrV69m6NChREVFMXToUEaMGAHAggULWLBgAaNHjwbc2fgVV1zBRx99RO3atZkyZcqpfY4ePZo33ngDgKFDh9K4cWOmT5+OMYZ58+Zx4MABrr32WjIyMkhMTKRz584MGzasSDHv27ePW2+9lfT0dNq3b8/48ePZs2cP1113HUePHqVNmzY8//zzfreVlrBu9iEpiV4VUlm6pRr79nkdjIiU1NSpU7nzzjtPNens2rWLV199lWnTpp2xmSc2NpbFixdz6NAhvv/++0LL7d+/n0WLFtGsWTOWLVvGwoUL6devH5MnTyY9Pb3IiR/giSee4Prrr2fRokX8/PPPzJo1i88//5yWLVuSlpZG586dycrK8ruttIT1mT8xMfRKPshjX0Qxb65l0GDdxSBSZMU8Qw+mPn360KFDh1M/R0dH88gjjxAfH09mZuZpP3v77bcD0KBBA44fP17kco0bN+avf/0rM2bMOHUlUVRr1qzh7rvvBqBjx46sWbOGu+66iwULFtC/f3+SkpKIioqiX79+BbaVlvA+8weSBjekMgeZ8/FBr0MRkRKqVKlSnp9Hjx7Niy++yNixYzl58mSxPlvUcpMnT+bVV18lNTWVXr16FSvexMRE0tLSAEhLSyMxMZEvv/ySG2+8kWnTpvHpp5+yefNmv9tKS3if+QPl+vagO/OZM7eb16GISIAMHDiQvn370qhRIzIzMzl27BixsbEB/Y62bdty9dVX06hRI+rVq8e4ceOoW7dukT77xz/+kSFDhvDss8/Svn17+vTpw7Zt27jlllvIyMigXr16NGjQgOjo6ALbSoux1pbal5VUu3btbInn87eWCTVHc//Pf2HLFijG6GeRiLN27VqaN2/udRhlwujRo5k/fz7ly5cnNjaWsWPHkpiY6HVYhfL3b2eMWWqtbeevfNif+WMMvXpkwf9g7qcnufOuaK8jEpEQMHr06GK39YeSsG/zB0gY1JLz2cWc//7sdSgiImVCRCR/06snvZjD3IVxlOKdVCIiZVZEJH/i4+ndYCN7f6nIihVeByMi4r3ISP5Az/5xAMz5JMPjSEREvBcxyb/OgPYksorZut9fpMzq2bMny5cvB2Du3LkMHjz4tOX9TaZ23333+S07dOhQtm3bVui+fFM95FbUieKKatu2bQwdOjRg+zsbEZP86dKFPtHz+GJlVU3xLFJGpaSkMHfuXADmzJlD3759i72PCRMmlOi7/SX/Nm3acMcdd5Rof2VdwJO/MSbGGPORMeZLY4zfKtMYk2SM2WmMSc1emgU6jgJiY0lp/QPHTpZnwYKgf5tIyHvgAejWLbDLAw+c/jv79u3LnDlzAHfm37dvX44cOUK/fv3o2LHjqSkYTif31cD27dvp1KkTPXv2ZN26dQCsXr2apKQk2rdvz/PPP8+BAwfo0qULy5cvp0uXLowbN+7U53NPEgewbNkyOnXqRFJSEu+8886p73vqqadITk7mqquuOmN8uW3dupXu3buTnJzMU089BcD69evp3LkzSUlJjBkzptBtZysYZ/4DgBXW2s5AHWPMxX7KVAeet9Z2yV7WByGOAi67rjZx/MLMjw6VxteJSDG1atWKzZs38+OPP3Ls2DEuuOACdu3axYgRI5g/fz5btmxh9+7dRd7fuHHjGDlyJDNnzmT//v1AwUnhqlatSmpqKm3atCE1NZWHH3640P3dc889vP3226SmpvLkk0+e2mdRJ4/Lb+TIkTz++OOkpaUxY8YM1q5dy7Rp0xg4cCBff/019evXB/C77WwFY5DXTGC6MSYGqAb4a2SvDlxrjLka+A4YZEthqHHsVX3oPmo+M6d3DvZXiYQ8r+Z169KlC2PGjDk1n05sbCxvvfUWb731Fvv37+doMdptt2zZQuvWrSlXrtypef6LMylcfunp6TRq1AiA5s2bs3XrVqDok8flt3btWjp27EhUVBTJycmsW7eOIUOGMGrUKPr3788VV1wB4Hfb2Qr4mb+19rC19hfgS2C3tXaLn2KbgD9ba5OBOkDX/AWMMcONMUuMMUv27NkTmOASEkipvpgNu6uxxV9UIuK5lJQUXnjhBVJSUgB4+eWXGTBgAO+++y4VK1Ys1r7q16/PqlWryMzMZOXKlUDhk8LFxcVx5MgRTnceGh8fz7Zt2zh+/Djr1q3jwuz5Yoo6eVx+LVq0IC0tDWstX3/9Nc2bN2fevHmMGjWKKVOmMG7cOE6cOOF329kK+Jm/MaYmcBjoBMwzxnS31s7PV2wbsCrX+rn592OtfQl4CdzcPgEKjpS+Ft6HmdMy+c394T+7hUio6d27NxUqVOCyyy479fPdd9/Niy++iDGG77//noYNGxZpXw899BA333wzTz/99KmJ3wqbFG748OH06NGDKlWqMHv2bL/7mzBhAjfddBMnTpxg5MiRVKtW7ayO9cknn+SOO+7gyJEjDB48mISEBA4fPsyQIUPIzMwkJSWFcuXK0aRJkwLbzlbAJ3YzxjwBrLHWvm2MmQFMsNZOz1dmDLABeAv4BrjBWrumsH2e1cRu+U2ZQpOrW9CiY1WmLKwVmH2KhAlN7Ba6ijuxWzA6fJ8F7jDGLALSgfXGmH/kK/Mf4HbgK2DS6RJ/wPXoQUrUbOYtqUKGxnuJSIQKeLuHtXYX0CPf5gfzlfkB6Bbo7y6SSpVIuWgnz66oQGoq9OzpSRQiZZa1FmP01LtQUpIWnMgZ5JVL9+vOpTwZzPxIo31FcouNjSU9Pb1EyUS8Ya0lPT292A+zCf+HufizZg29E3fx4/lt+XZXjcDtVyTEnThxgp07d3Ls2DGvQ5FiiI2NpV69egU6giP7YS7+NG9OSrWPefD73nz3HVxwgdcBiZQN5cqVO3X7ooS3iGz2wRhServ7e2d9UrxBHiIi4SAykz/Q4qaLuYAdzHh3n9ehiIiUuohN/qZnD/pFzWL2V1UoxmhsEZGwELHJn8qVufKibRw6Hstnn3kdjIhI6Yrc5A/0vMnN8jn17QNehyIiUqoiOvnHXXs5PZnLtE8gBO54FREJmIhO/jRuzJV1lrI1vSprSm+CCRERz0V28geuuKY8AFM/0qAWEYkcEZ/8697UlUtYytT3DnsdiohIqYn45E+HDlwZN5dFG2qwd6/XwYiIlA4l/+horux5BEsU06eePHN5EZEwoOQPtLmtNXX4nqkTNdpXRCKDkj8QldKH/lEzmLWoskb7ikhEUPIHqFSJK1vv4NDxWD7/3OtgRESCT8k/W89b6xLLUaa++bPXoYiIBJ2Sf7ZzBqbQizn837QojfYVkbCn5O9Tvz4DL1jC9p+rsny518GIiASXkn8uV95YiWgy+fhNDfgSkfCm5J9L/JB+dOUzPv7ghNehiIgElZJ/bomJDKyVytofq7N2rdfBiIgEj5J/bsYw4Do30dukd37xOBgRkeBR8s+n7m296MAiPlbyF5EwpuSfX7t2DKw6j6Xb4tm+3etgRESCQ8k/P2O4ZoC70X/Se5rjX0TCk5K/H03uuIxWrODjiYe8DkVEJCiU/P3p3JmBFWeRuq4mu3d7HYyISOAp+fsTHc3AfkexRDHpQ93zLyLhR8m/EC3v7EgCa/ngpQNehyIiEnABT/7GmBhjzEfGmC+NMa8VUibWGDPNGLPCGPOWMcYEOo6zZXp054a4/+OzVTX4/nuvoxERCaxgnPkPAFZYazsDdYwxF/spcwuw01rbGqgO9A5CHGenXDmu7/8Llig+ekdPeBGR8BKM5D8T+KcxJgaoBhz0U6YHMDt7fR7QPQhxnLWEEd25mOW8/7Lu+hGR8BLw5G+tPWyt/QX4Ethtrd3ip1hNwNeYfhCokb+AMWa4MWaJMWbJnj17Ah1m0Vx2GTdU+oS0jTXZutWbEEREgiEYbf41jTEVgE5AdWOMv7P6vUDV7PWq2T/nYa19yVrbzlrbrlatWoEOs2iio7l+0EkAPnzzqDcxiIgEQTCaff4ADLbWngR+AeL8lJkL9Mle7wHMD0IcAdHwrr50YBHvv6bkLyLhIxjJ/1ngDmPMIiAdWG+M+Ue+Mu8AdY0xK4F9uMqgbGrfnhuqf8o3O2qwbp3XwYiIBEYw2vx3WWt7WGs7WmtvsdZuttY+mK9MhrW2v7W2lbV2iLVl+Km5xjD4xhgMWXzw+hGvoxERCQgN8iqC84f3pyuf8c4bJ/RwdxEJC0r+RdGqFbfWns3Gn6qRluZ1MCIiZ0/JvyiMYdCw6pzDESZO8DdsQUQktCj5F1HlO69nIB/zwaRyHNM0/yIS4pT8i6p+fW67eCX7j8Ux5f/U8C8ioU3Jvxi6P9CaenzHxPE/ex2KiMhZUfIvhuhB1zCk3AfM/KoaP/zgdTQiIiWn5F8cFStyW/90smwU77yumT5FJHQp+RdTs/vddA+vP/eL7vkXkZCl5F9cl13GnTUmsWZXNRYu9DoYEZGSUfIvrqgobri7GlU4wIv/0Dz/IhKalPxLoOKIW7mFd/hwaiz79nkdjYhI8Sn5l0S9etzVdR0ZJ8vx5usnvY5GRKTYlPxLqNVDKXRgES/884g6fkUk5Cj5l1TfvtxV47+s/74Kn3/udTAiIsWj5F9S0dFcd08tqrJfHb8iEnKU/M/COXffylAzkf9Oj9OIXxEJKUr+Z+P887mv1zoys6J47pkTXkcjIlJkSv5nqfEj13MVU3jh2UyO6hnvIhIilPzPVteuPNB4GnsPx/HO27rtR0RCg5L/2TKGro90pjXfMP4J3fYpIqFByT8AzE038rvKr7J6WyXmzvU6GhGRM1PyD4TYWG64rxbn8SP/+tsRr6MRETkjJf8AqXDfcO6JeoHpn1Vk5UqvoxEROT0l/0CpXZt7B++mMgd54rEMr6MRETktJf8Aqv7ne/kNz/Hh5PJs2OB1NCIihVPyD6TERH6Xso4KHGPsXzXoS0TKLiX/ADvvL79hGC/z1rtRbN/udTQiIv4p+QdacjIju6Rhsk7y1N8zvY5GRMQvJf8guODxYdzGRF55FXbu9DoaEZGClPyDoVs3/nTJDLIys/jraD3pS0TKnqAkf2PMRGNMmjFmijEmxs/7ScaYncaY1OylWTDi8IwxNBgznLt5gVdfN2zc6HVAIiJ5lSj5G2N+c5r3ugAx1toOQBWgj59i1YHnrbVdspf1JYmjTOvbl0eTZlPBHuOxP6ntX0TKlpKe+Q89zXu7gWfOsP/qwLXGmMXGmP8ZY0wJ4yi7jOG8px7kAfsv3vswhhUrvA5IRCRHwJt9rLUbrbWLjTHXAFnAp36KbQL+bK1NBuoAXfMXMMYMN8YsMcYs2bNnT6DDLB1du/Jgt6VUM/v50yid/YtI2VGgPT43Y8xN/jYDNc7wuauA+4ErrbX+st42YFWu9XPzF7DWvgS8BNCuXbuQnSi5+rhRPNx+LH+cOZb586F7d68jEhE585n/r/wsTYC3CvuAMaY2MBLob60t7MnmvwduMMZEAS3JqQjCT3Iyv71yKw3Mdn53XyYndfOPiJQBpz3zt9b+xd/203X4ArfhmnJmZTflvw40t9Y+mKvMf4D3gHuBSdbaNcUJOtTEjRvNuGmjuGH1e7z+Otx5p9cRiUikM7YEj54yxizObq8vFe3atbNLliwpra8LCnvPvXR57iY21Uxm45YYqlTxOiIRCXfGmKXW2nb+3tMgr1JiRj/G+IqP8lN6DH//u9fRiEikC0qHr/hRqxZJo6/g1pET+efTQ7j99iiaNvU6KBGJVEXp8G2SvfjWGwNvBjmu8HTffYyt/zyxJ49wz2+y9LB3EfFMUZp9TPZige7AaKBb8EIKYxUqUGf8wzyRNYo5c6N4/32vAxKRSHXa5J99t8/fge+AK4AdwCXW2h6lEFt4GjCAu1O20y5qKb/77Un27/c6IBGJRKdN/saYMbjEfzMwDngROMcY06kUYgtPxhD9n2d4Ifpe9uw1PPqo1wGJSCQ6U7PP+cB03Bn/lcCw7EV3qp+Nxo1p+6d+3Gsn8Pzzlq++8jogEYk0JbrPv7SFw33+BRw7xsHEjiTumE7lJuexbHkUsbFeByUi4UT3+ZdFsbFUeX4cr2QOZe26KP7idyy1iEhwKPl7qU8f+g45j1+b13jyScvixV4HJCKRQsnfa+PH83StsZwfvZuht1mOHfM6IBGJBEr+XqtRg6ovPskrJ25j7TrDY495HZCIRAIl/7JgwAD63lCDYeYVnnrKMn++1wGJSLhT8i8rJkzgXzX/xq/K72DIEEt6utcBiUg4U/IvK+LjqfjC07yXcQ0//XCSYcPQ3D8iEjRK/mXJtddyye0X8/esUUyaBC+/7HVAIhKulPzLmn//m981nkLvCp/zwAOWNWH9jDMR8YqSf1lTqRJR777NxMybqZR1kGuvtRwq7EnIIiIlpORfFiUnU+fxEbyfcQ0b1lt+/Wu1/4tIYCn5l1UPP0yPbpYnov8fH30E48d7HZCIhBMl/7IqOhrefZeHarzCgIqzGTnS8sUXXgclIuFCyb8sq1MH88H7vPHLdTSK+4HrrrPs3Ol1UCISDpT8y7pu3aj691FMOtybIz8f56qr4MgRr4MSkVCn5B8KHnqIxKua8P6JQaxYYbnlFsjK8jooEQllSv6hwBiYOJHLG6/n6bg/M3kyevyjiJwVJf9QUa0aTJnCb6P/w/AaHzF2LLzxhtdBiUioUvIPJQkJmI8+5D/7h9AzfgXDhlmmT/c6KBEJRUr+oaZPH8qNf4qP917KRTW/Z9AgWLTI66BEJNQo+Yeie++lyt03M2P3JdStdIArroDVq70OSkRCiZJ/KDIGJkzgvP7JfLqnDRXsMfr2hW3bvA5MREKFkn+oiomBDz7gwo61mXWkC0cOnKB7d9i+3evARCQUBCX5G2MmGmPSjDFTjDExft6PNcZMM8asMMa8ZYwxwYgj7J1zDkydSqsmvzDb9mZ/eibduqkCEJEzC3jyN8Z0AWKstR2AKkAfP8VuAXZaa1sD1YHegY4jYtSsCTNn0q7aJmbHXM7+fSdVAYjIGQXjzH838MwZ9t8DmJ29Pg/oHoQ4Ikf9+jBnDu3Kr2R2uSvYv+8kXbvCxo1eByYiZVXAk7+1dqO1drEx5hogC/jUT7GawIHs9YNAjfwFjDHDjTFLjDFL9uzZE+gww09CAsybR7uoZcwpfwVHDp6kc2dYtszrwESkLApWm/9VwP3AldbaTD9F9gJVs9erZv+ch7X2JWttO2ttu1q1agUjzPDTogXMm0dbu4TU8j04p/wJunWDefO8DkxEyppgtPnXBkYC/a21hT2AcC45fQE9gPmBjiNitWwJc+fSLHM1X2Yk0eC8o/TrBx984HVgIlKWBOPM/zagDjDLGJNqjPm1MeYf+cq8A9Q1xqwE9uEqAwmU1q3hiy+oG5vO5z8lkJxwgBtugMce02ygIuIYGwIPh23Xrp1dsmSJ12GEnh07oHdvMnbsZsSlq3h9dj0GDoQ334SKFb0OTkSCzRiz1Frbzt97GuQVzurXhy++oELzRrw6tyH/HLyIyZOhc2fYssXr4ETES0r+4e7cc2HBAkzfPvzuo058cvVLbN9uadMG/vtfr4MTEa8o+UeCKlVgyhT47W9JmXQXy9v8moRfnWTwYLjnHjh2zOsARaS0KflHipgYGD8ennuOhp+/yRdHLuEPQ9N57jno0AFWrvQ6QBEpTUr+kWbECJg9m/L7fuQfH9Zn6h8W8MMP0K4djBkDmf5GZYhI2FHyj0Tdu8Py5dC2Lf2f7s7qlD8w8OpM/vQn6NgRVq3yOkARCTYl/0h1/vlu6O9DDxH/5j95f01rPhy7hW3boE0bePBBOFTYED0RCXlK/pEsJgbGjYOZM2H/fgb/qRlr73yaobdm8fTTbrqgDz+EEBgKIiLFpOQv0Leva+sZPJj4sQ/y8upOLHpnC+edB9df71qJvvrK6yBFJJCU/MWpXh3efRfefx82bqTDbc34us+jPDf+OGvXujuCBg2C9eu9DlREAkHJX/K6/npYtw5uvpnocU8w4pkENj//KaNHw6xZkJgIw4drhLBIqFPyl4Jq1YI33oD586FCBSpd25fHvu7Ppk/WM2IETJwITZvCrbfC2rVeBysiJaHkL4Xr1g2++QaefBJSUzmvRyITMkew5as93H8//O9/7kpg0CD1CYiEGiV/Ob0KFWDkSNi0yQ0Qe+UV6l7WmH9WGc22FQd45BGYPdv1CbRvD2+/DRkZXgctImei5C9FEx8PEya4u4J694a//IVa7Rrwt+jH2Pntz/znP3DgAAwZAg0auGcH7NjhddAiUhglfymeZs1ce88330DPnvD441S+qCH3/Phn1iz4iVmz3FQRf/0rNGwIffrAe+/B0aNeBy4iuSn5S8m0bu0qgRUr3JXA3/5GVMP69PnwTqaNW82WLe7sf8MGuOkmqFPHtRp9+aWeJiZSFij5y9lp1co9GGDdOrjjDjdWoGVLGt6dwmPtZ7JlUxZz58KVV7q7hLp0cc1Cv/89pKVp9LCIV/QYRwms9HR48UXXP/Djj67t58474fbbOVT5fKZOdQ+TnzkTjh93Dxu77jq4+mo3qVx0tNcHIBI+TvcYRyV/CY6MDJg8GV56yU0gFx0N/fvDsGHQpw/7j5RjyhQ3d9Cnn8KJE1CjBlx+ubtK6NsXqlb1+iBEQpuSv3hr0yZ45RV4/XX46Sc3iOy661xnQMeOHDho+PRTmDoVpk93Fw8xMXDppa4y6NnTdTFEqZFSpFiU/KVsOH4cZsxw/QJTprjnRzZs6CqBG2+ExEROZhnS0mDaNFcZrF7tPhofDz16QK9ebrnwQk+PRCQkKPlL2XPoEEya5CqC2bPdLUBNmsCAAXDNNW7UWFQUu3a5VqM5c9zy/ffu440auQHIl17qOpEbNwZjPD0ikTJHyV/Ktt27Xf/A5Mkwd67rADjvPNcLfNVVbk7pc87BWndTka8i+OIL+Plnt4vatV0l4Ftat3ZNRyKRTMlfQseBA65paNIk1wFw+LCbYuKyyyAlxfUEt2gBxpCV5SaWS011yxdfwPbtbjcVK0Jycs6SlAT16unqQCKLkr+EpowM+OwzN5f0zJmwZo3bXq+eqwh69YKuXd1pf7bvvnMDyVJT3WRzK1a4CwlwxXJXBklJ7jEGIuFKyV/Cw44driKYNcv1Exw86LYnJLgOgG7dClQGx465CuDrr2HxYrfkfiBN48Zw8cVuad3aveoKQcKFkr+En8xMWLYMFixwS2pqzhPnmzVzFUGnTm7kWJMmebL5/v2wdKmrCJYtc9MUbdqUs+saNXIqBN+SkADlypXmAYqcPSV/CX+ZmbB8ed7KwHdlEB/v7h7q2NEtSUlQqVKejx86BN9+6yoC3/Ltt+7KAaB8eVcBJCbmXRo10qhkKbuU/CXynDzp+gjS0mDRIresW+fei4qCiy5yDyBo29YtLVu6juVcMjPdxHQrVrjKYNUqN+7A16kMEBvrKoWWLfNWCg0balCaeE/JXwRg3z7X1uOrDL7+2rUBgWvTadkSLrkkp0K46CKIiyuwm0OH3F1Gq1e7xVcp7NyZU+acc1yl0KyZW3zrTZu690RKQ6knf2NMOeBja+2VhbyfBEwCtmVv+rW1dr2/sqDkL0FiLWzd6hr+ly7NWfbtc+9HR7vT+Nat3eylF13kljp1/PYIHzjgLjZ8lcLata5zefv2vLOXXnBBwUqhWTPX0ayrBQmkUk3+xpg44CugqbU2tpAyfYAka+2YouxTyV9KjbXurqKlS3MqhZUrc4YWg+sRzl0ZtGrlKol8/Qg+R4/Cxo2uIvAt69a5V18fNbiLjKZNcyqDpk1dX3WTJlCzpu5AkuLzpNnHGLPJWtukkPeuBx4GMoHvgEH2NIEo+Yvn0tNdD/C337rK4NtvXXvPkSM5ZRo1ck1HzZu7JSHBvVap4neX1rpZr/1VCtu25X3oTbVqORWBb/nVr9xrrVqqGMS/spj82wK1rbWfGGMWAo9YaxfkKzMcGA5Qv379tttz97KJlAVZWS5L+yqDb7917T0bN+aMLAM4//y8lYFvqV270KydkeFapDZtcrvbtClnyV8xVK5csELwLaf5CokAZTH51wQOW2szjDHvApOttR8Wti+d+UtIOXECtmxxp/Fr17rFt567nadqVVchJCS4rO1bmjRxGb0Qx4+7CiB3heCrILZudTc6+VSsWPCKwbecf776GMJdWUz+Y4ANwFvAN8AN1to1he1LyV/CgrWu7yB3ZeDrFc7dpwDulD13hZC7YjjN7UInTrgui/xXCxs3urxUMfMAAAmvSURBVIoh9wVJbKwb4eyvOalePY1fCAeeJn9jzIXAPdbaB3O9Vwd4D6gITLfWPna6fSn5S9g7ciQnS+dfdu/OW7Zu3YKVQqNGbimk0xncuIUdO2Dz5rwVw6ZNbltGRk7Z8uXd7vxdMTRooBlTQ4Xu8xcJZQcP5m3byV0x7NmTt+y55+ZUBI0b512vU6fQdp6sLNi1q2Cl4Ft++SWnbEyMG8Tmr2Jo2LDAWDnxkJK/SLjav99l5y1b8i6bN7vT/Nw9wxUquEeg+asYLryw0OYk311J/iqFjRvzdmNERUH9+v4rhkaN/I6ZkyBS8heJRL4OgM2bC1YMmzfnzdrg+hlyVwq5K4lCbhuyFvbuLfyKwTdezqdePf8VQ+PGp22xkhJS8heRvKx1mTl3xZB7/bvv8g5LjosrvDmpYUPXe+yH7yv8VQw//ZS3bO3aOZWB767YhAT3NepjKBklfxEpnowMNy/F5s3uNiFfxeB7zT24zRjXCZ2/cvC9xsf7vWo4eNB/xbBhg2tm8ilXzvVp++6K9VUKzZqd9o5YQclfRALJWtfRnL9C8K3nv221cmX/TUmNG7sOgvLlC3zF/v05I559d8auW+cqh9zjGOrVy1spNG/uBlnXqhXk30GIUPIXkdJz9KgbhZa/cvBdRfgekgCuh/iCCwpeLfjW8z1n8/hxt5vclYLv9fDhnHLnnZcz9ZJvadEi8mZUVfIXkbIhK8u16fjra9i8uWBHQLVqriL41a/yznjXtGmeOZN84+fWrMmZacM324avrjHG9SfkrxSaNAnfkc5K/iISGg4fLtjHsHmzu6c0/6RGtWvnrRB8rxdeeOqZmydPuo/7KoNVq9zrpk05u6pUyT2qs21b9ziHSy5xzUjh0Mms5C8ioS8jw2Vy3xSoGzbkvO7dm1MuJsY1GTVtmvcxa82bn2r3OXrUXSWsXOme/rl0qXtam28wW2yse4yDrzK45BK3i1AbwKbkLyLhbd++nMogf8Vw/LgrY4xrQkpMzPvczYQEqFCBkydd8WXLch7lsHx5zqOgy5VzVwgdOrgngHbo4HZXlmdNVfIXkciUmemuFnzP2vS9btjg3gM3g12TJq4iaNUK2rRxS716ZFnDli2uMliyBL76yr36rhDi411F4FuSk103RVmh5C8iktvx464CyF0hrFrlOgN8ObFmTXeq36ZNzmuzZmTaaFavdhVBWpp7Xbs252MJCa4i6NgROnd2dxl51aGs5C8iUhSHD7uOgG++cW0+y5e7HmJf01FcnLs6uPhiaNfOneq3aMGBIzEsWZJTGXz1Vc6NS9Wq5VQEXbpAUlLp3XKq5C8iUlInTriBBL7KYPlyVzkcOODeP+ccd6tQcrJb2rfHXlCfLVsNX37JqWX1alc8JsZ1IPsqg86d3biEYFDyFxEJJGtdE9HixTnL8uU5D0U499ycyiA5GZKS2EcNFi3KqQwWL84Zg9C4cd7KICEhME1FSv4iIsF2/LhrIspdIeTuDGjWDDp1cm1AnTpxvHFzln0TdaoySE3NeTxD9equaOfOcPnl7rbTklDyFxHxwsGD7p7RtDRYtMgtvjEJVau6+0WzKwOb3J5NP1XJUxmsWwePPAJjxpTs65X8RUTKAl9z0cKFriJYuNDdZWStGzDQsmWeq4P06k04mWU499ySfZ2Sv4hIWXXggGsiWrjQLWlpOSPL4uNh1Cj4wx9KtOvTJf8wmL1CRCSEVa0KvXu7BdykQ2vW5FwZ1K0blK9V8hcRKUuiolzzT8uWMGxY8L4maHsWEZEyS8lfRCQCKfmLiEQgJX8RkQik5C8iEoGU/EVEIpCSv4hIBFLyFxGJQCExvYMxZg+wvYQfjwf2nrFUeNExRwYdc2Q4m2NuYK2t5e+NkEj+Z8MYs6SwuS3ClY45MuiYI0OwjlnNPiIiEUjJX0QkAkVC8n/J6wA8oGOODDrmyBCUYw77Nn8RESkoEs78RUQkHyV/EZEIFLbJ3xgTa4yZZoxZYYx5yxhjvI4p0IwxE40xacaYKcaYSvmPN1x/B8aY3xtj5hhj4o0xXxhjvjXGjM1+r8C2UGeMeSj733mGMebccD9mY0xFY8z/GWO+NMY8Ge7/zsaYcsaYqdnrBf5mi7qtuN8btskfuAXYaa1tDVQHenscT0AZY7oAMdbaDkAV4A4KHm/Y/Q6MMQ2A27J/fAD4BGgN9DPGNC1kW8gyxjQCErP/nWcA4wnzYwZuBtKstZ2BROBFwvSYjTFxwFJy/jb9/c0WdVuxhHPy7wHMzl6fB3T3MJZg2A08k70eBYym4PGG4+/gGeCP2es9gNnW2izgM3Idc75toawnUN0Y8zlwKXAh4X/M+4FKxphoIA7oRJges7X2qLW2FbAze5O/v9mibiuWcE7+NYED2esHgRoexhJw1tqN1trFxphrgCxgOQWPN6x+B8aYm4AVwJrsTf6OL6yOGagF7LHWXgbUA5IJ/2OeBKQAm4G1uGMK92P2Ker/6bM+/nBO/nuBqtnrVQnD+UCMMVcB9wNXAj9S8HjD7XfQH3cm/D7QFjfnSbgf80Fgffb6FmAb4X/MfwSet9Y2xCW1poT/Mfv4O66ibiuWcE7+c4E+2es9gPkexhJwxpjawEigv7X2EP6PN6x+B9bam6y1XYAbcO2kzwJ9jDFRQFdyHXO+baFsKeCb16UJriII92OuDBzLXs8AFhH+x+xT1L/js/7bDufk/w5Q1xizEtiH+2WFk9uAOsAsY0wqUI6Cxxvuv4N/A5cDK4FPrLWbCtkWsqy1i4B0Y8zXuMR/K2F+zLhKfYQxZhGuzf8awv+Yffz9zRZ1W7FohK+ISAQK5zN/EREphJK/iEgEUvIXEYlASv4iIhFIyV8kH2PMUGPMdmNMavbS7yz3NTSA4YkERIzXAYiUUS9ba//mdRAiwaLkL3IGxpjRuGkVqgK7gBtxfztvAPWB7cBQ3JX0G0ADYA9wffYuLjLGfAacCwyy1q4uteBFCqFmHxH/fm2MWWCMWQDUBRZmzzKZDlwNDAPWZG/bCNwODAdWWGs7AlOAVtn76oibdXFs9mdFPKfkL+Lfq9babtbabriz/a+zt3+Dm1mzBW7aAbJfWwAJwOLsba8BS7LX37XWHsddIZQPfugiZ6bkL1I07bNfL8HNNrka6JC9rUP2z+tylXsUdzUAcLiUYhQpMrX5i/g3zBiTkr1+EfBZ9hxKO4GpZLf5G2O+xJ3RPwFEAxOzy/0EPIWbhE6kzNHcPiJnkN3hu8Bau8DjUEQCRslfRCQCqc1fRCQCKfmLiEQgJX8RkQik5C8iEoGU/EVEItD/BzjPvVLhK9t1AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "# Hyper-parameters\n",
    "num_epochs = 1000\n",
    "\n",
    "# Initialize a new network\n",
    "params = init_rnn(hidden_size=hidden_size, vocab_size=vocab_size)\n",
    "\n",
    "# Initialize hidden state as zeros\n",
    "hidden_state = np.zeros((hidden_size, 1))\n",
    "\n",
    "# Track loss\n",
    "training_loss, validation_loss = [], []\n",
    "\n",
    "# For each epoch\n",
    "for i in range(num_epochs):\n",
    "    \n",
    "    # Track loss\n",
    "    epoch_training_loss = 0\n",
    "    epoch_validation_loss = 0\n",
    "    \n",
    "     # For each sentence in validation set\n",
    "    for inputs, targets in validation_set:\n",
    "        \n",
    "        # One-hot encode input and target sequence\n",
    "        inputs_one_hot = one_hot_encode_sequence(inputs, vocab_size)\n",
    "        targets_one_hot = one_hot_encode_sequence(targets, vocab_size)\n",
    "        \n",
    "        # Re-initialize hidden state\n",
    "        hidden_state = np.zeros_like(hidden_state)\n",
    "\n",
    "        # Forward pass\n",
    "        # YOUR CODE HERE!\n",
    "        outputs, hidden_states = forward_pass(inputs_one_hot, hidden_state, params)\n",
    "\n",
    "        # Backward pass\n",
    "        # YOUR CODE HERE!\n",
    "        loss, _ = backward_pass(inputs_one_hot, outputs, hidden_states, targets_one_hot, params)\n",
    "        \n",
    "        # Update loss\n",
    "        epoch_validation_loss += loss\n",
    "    \n",
    "    # For each sentence in training set\n",
    "    for inputs, targets in training_set:\n",
    "        \n",
    "        # One-hot encode input and target sequence\n",
    "        inputs_one_hot = one_hot_encode_sequence(inputs, vocab_size)\n",
    "        targets_one_hot = one_hot_encode_sequence(targets, vocab_size)\n",
    "        \n",
    "        # Re-initialize hidden state\n",
    "        hidden_state = np.zeros_like(hidden_state)\n",
    "\n",
    "        # Forward pass\n",
    "        # YOUR CODE HERE!\n",
    "        outputs, hidden_states = forward_pass(inputs_one_hot, hidden_state, params)\n",
    "\n",
    "        # Backward pass\n",
    "        # YOUR CODE HERE!\n",
    "        loss, grads = backward_pass(inputs_one_hot, outputs, hidden_states, targets_one_hot, params)\n",
    "        \n",
    "        if np.isnan(loss):\n",
    "            raise ValueError('Gradients have vanished!')\n",
    "        \n",
    "        # Update parameters\n",
    "        params = update_parameters(params, grads, lr=3e-4)\n",
    "        \n",
    "        # Update loss\n",
    "        epoch_training_loss += loss\n",
    "        \n",
    "    # Save loss for plot\n",
    "    training_loss.append(epoch_training_loss/len(training_set))\n",
    "    validation_loss.append(epoch_validation_loss/len(validation_set))\n",
    "\n",
    "    # Print loss every 100 epochs\n",
    "    if i % 100 == 0:\n",
    "        print(f'Epoch {i}, training loss: {training_loss[-1]}, validation loss: {validation_loss[-1]}')\n",
    "\n",
    "\n",
    "# Get first sentence in test set\n",
    "inputs, targets = test_set[1]\n",
    "\n",
    "# One-hot encode input and target sequence\n",
    "inputs_one_hot = one_hot_encode_sequence(inputs, vocab_size)\n",
    "targets_one_hot = one_hot_encode_sequence(targets, vocab_size)\n",
    "\n",
    "# Initialize hidden state as zeros\n",
    "hidden_state = np.zeros((hidden_size, 1))\n",
    "\n",
    "# Forward pass\n",
    "outputs, hidden_states = forward_pass(inputs_one_hot, hidden_state, params)\n",
    "output_sentence = [idx_to_word[np.argmax(output)] for output in outputs]\n",
    "print('Input sentence:')\n",
    "print(inputs)\n",
    "\n",
    "print('\\nTarget sequence:')\n",
    "print(targets)\n",
    "\n",
    "print('\\nPredicted sequence:')\n",
    "print([idx_to_word[np.argmax(output)] for output in outputs])\n",
    "\n",
    "# Plot training and validation loss\n",
    "epoch = np.arange(len(training_loss))\n",
    "plt.figure()\n",
    "plt.plot(epoch, training_loss, 'r', label='Training loss',)\n",
    "plt.plot(epoch, validation_loss, 'b', label='Validation loss')\n",
    "plt.legend()\n",
    "plt.xlabel('Epoch'), plt.ylabel('NLL')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 生成序列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Example:\n",
      "['a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b']\n"
     ]
    }
   ],
   "source": [
    "def freestyle(params, sentence='', num_generate=4):\n",
    "    \"\"\"\n",
    "    Takes in a sentence as a string and outputs a sequence\n",
    "    based on the predictions of the RNN.\n",
    "    \n",
    "    Args:\n",
    "     `params`: the parameters of the network\n",
    "     `sentence`: string with whitespace-separated tokens\n",
    "     `num_generate`: the number of tokens to generate\n",
    "    \"\"\"\n",
    "    sentence = sentence.split(' ')\n",
    "    \n",
    "    sentence_one_hot = one_hot_encode_sequence(sentence, vocab_size)\n",
    "    \n",
    "    # Initialize hidden state as zeros\n",
    "    hidden_state = np.zeros((hidden_size, 1))\n",
    "\n",
    "    # Generate hidden state for sentence\n",
    "    outputs, hidden_states = forward_pass(sentence_one_hot, hidden_state, params)\n",
    "    \n",
    "    # Output sentence\n",
    "    output_sentence = sentence\n",
    "    \n",
    "    # Append first prediction\n",
    "    word = idx_to_word[np.argmax(outputs[-1])]    \n",
    "    output_sentence.append(word)\n",
    "    \n",
    "    # Forward pass\n",
    "    for i in range(num_generate):\n",
    "\n",
    "        # Get the latest prediction and latest hidden state\n",
    "        output = outputs[-1]\n",
    "        hidden_state = hidden_states[-1]\n",
    "    \n",
    "        # Reshape our output to match the input shape of our forward pass\n",
    "        output = output.reshape(1, output.shape[0], output.shape[1])\n",
    "    \n",
    "        # Forward pass\n",
    "        outputs, hidden_states = forward_pass(output, hidden_state, params)\n",
    "        \n",
    "        # Compute the index the most likely word and look up the corresponding word\n",
    "        word = idx_to_word[np.argmax(outputs)]\n",
    "        \n",
    "        output_sentence.append(word)\n",
    "        \n",
    "    return output_sentence\n",
    "    \n",
    "# Perform freestyle\n",
    "print('Example:')\n",
    "print(freestyle(params, sentence='a a a a a b'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2、LSTM"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- $i = \\sigma ( W^i [h_{t-1}, x_t])$\n",
    "- $f = \\sigma ( W^f [h_{t-1},x_t])$\n",
    "- $o = \\sigma ( W^o [h_{t-1},x_t])$\n",
    "- $g = \\mathrm{tanh}( W^g [h_{t-1}, x_t])$\n",
    "- $c_t = c_{t-1} \\circ f + g \\circ i$\n",
    "- $h_t = \\mathrm{tanh}(c_t) \\circ o$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 初始化权重"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Size of concatenated hidden + input vector\n",
    "z_size = hidden_size + vocab_size \n",
    "\n",
    "def init_lstm(hidden_size, vocab_size, z_size):\n",
    "    \"\"\"\n",
    "    Initializes our LSTM network.\n",
    "    \n",
    "    Args:\n",
    "     `hidden_size`: the dimensions of the hidden state\n",
    "     `vocab_size`: the dimensions of our vocabulary\n",
    "     `z_size`: the dimensions of the concatenated input \n",
    "    \"\"\"\n",
    "    # Weight matrix (forget gate)\n",
    "    W_f = np.random.randn(hidden_size, z_size)\n",
    "    \n",
    "    # Bias for forget gate\n",
    "    b_f = np.zeros((hidden_size, 1))\n",
    "\n",
    "    # Weight matrix (input gate)\n",
    "    W_i = np.random.randn(hidden_size, z_size)\n",
    "    \n",
    "    # Bias for input gate\n",
    "    b_i = np.zeros((hidden_size, 1))\n",
    "\n",
    "    # Weight matrix (candidate)\n",
    "    W_g = np.random.randn(hidden_size, z_size)\n",
    "    \n",
    "    # Bias for candidate\n",
    "    b_g = np.zeros((hidden_size, 1))\n",
    "\n",
    "    # Weight matrix of the output gate\n",
    "    W_o = np.random.randn(hidden_size, z_size)\n",
    "    b_o = np.zeros((hidden_size, 1))\n",
    "\n",
    "    # Weight matrix relating the hidden-state to the output\n",
    "    W_v = np.random.randn(vocab_size, hidden_size)\n",
    "    b_v = np.zeros((vocab_size, 1))\n",
    "    \n",
    "    # Initialize weights according to https://arxiv.org/abs/1312.6120\n",
    "    W_f = init_orthogonal(W_f)\n",
    "    W_i = init_orthogonal(W_i)\n",
    "    W_g = init_orthogonal(W_g)\n",
    "    W_o = init_orthogonal(W_o)\n",
    "    W_v = init_orthogonal(W_v)\n",
    "\n",
    "    return W_f, W_i, W_g, W_o, W_v, b_f, b_i, b_g, b_o, b_v\n",
    "\n",
    "\n",
    "params = init_lstm(hidden_size=hidden_size, vocab_size=vocab_size, z_size=z_size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 前向传播"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input sentence:\n",
      "['a', 'a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b']\n",
      "\n",
      "Target sequence:\n",
      "['a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'EOS']\n",
      "\n",
      "Predicted sequence:\n",
      "['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'EOS']\n"
     ]
    }
   ],
   "source": [
    "def forward(inputs, h_prev, C_prev, p):\n",
    "    \"\"\"\n",
    "    Arguments:\n",
    "    x -- your input data at timestep \"t\", numpy array of shape (n_x, m).\n",
    "    h_prev -- Hidden state at timestep \"t-1\", numpy array of shape (n_a, m)\n",
    "    C_prev -- Memory state at timestep \"t-1\", numpy array of shape (n_a, m)\n",
    "    p -- python list containing:\n",
    "                        W_f -- Weight matrix of the forget gate, numpy array of shape (n_a, n_a + n_x)\n",
    "                        b_f -- Bias of the forget gate, numpy array of shape (n_a, 1)\n",
    "                        W_i -- Weight matrix of the update gate, numpy array of shape (n_a, n_a + n_x)\n",
    "                        b_i -- Bias of the update gate, numpy array of shape (n_a, 1)\n",
    "                        W_g -- Weight matrix of the first \"tanh\", numpy array of shape (n_a, n_a + n_x)\n",
    "                        b_g --  Bias of the first \"tanh\", numpy array of shape (n_a, 1)\n",
    "                        W_o -- Weight matrix of the output gate, numpy array of shape (n_a, n_a + n_x)\n",
    "                        b_o --  Bias of the output gate, numpy array of shape (n_a, 1)\n",
    "                        W_v -- Weight matrix relating the hidden-state to the output, numpy array of shape (n_v, n_a)\n",
    "                        b_v -- Bias relating the hidden-state to the output, numpy array of shape (n_v, 1)\n",
    "    Returns:\n",
    "    z_s, f_s, i_s, g_s, C_s, o_s, h_s, v_s -- lists of size m containing the computations in each forward pass\n",
    "    outputs -- prediction at timestep \"t\", numpy array of shape (n_v, m)\n",
    "    \"\"\"\n",
    "    assert h_prev.shape == (hidden_size, 1)\n",
    "    assert C_prev.shape == (hidden_size, 1)\n",
    "\n",
    "    # First we unpack our parameters\n",
    "    W_f, W_i, W_g, W_o, W_v, b_f, b_i, b_g, b_o, b_v = p\n",
    "    \n",
    "    # Save a list of computations for each of the components in the LSTM\n",
    "    x_s, z_s, f_s, i_s,  = [], [] ,[], []\n",
    "    g_s, C_s, o_s, h_s = [], [] ,[], []\n",
    "    v_s, output_s =  [], [] \n",
    "    \n",
    "    # Append the initial cell and hidden state to their respective lists\n",
    "    h_s.append(h_prev)\n",
    "    C_s.append(C_prev)\n",
    "    \n",
    "    for x in inputs:\n",
    "        \n",
    "        # Concatenate input and hidden state\n",
    "        z = np.row_stack((h_prev, x))\n",
    "        z_s.append(z)\n",
    "        \n",
    "        # Calculate forget gate\n",
    "        f = sigmoid(np.dot(W_f, z) + b_f)\n",
    "        f_s.append(f)\n",
    "        \n",
    "        # Calculate input gate\n",
    "        i = sigmoid(np.dot(W_i, z) + b_i)\n",
    "        i_s.append(i)\n",
    "        \n",
    "        # Calculate candidate\n",
    "        g = tanh(np.dot(W_g, z) + b_g)\n",
    "        g_s.append(g)\n",
    "        \n",
    "        # Calculate memory state\n",
    "        C_prev = f * C_prev + i * g \n",
    "        C_s.append(C_prev)\n",
    "        \n",
    "        # Calculate output gate\n",
    "        o = sigmoid(np.dot(W_o, z) + b_o)\n",
    "        o_s.append(o)\n",
    "        \n",
    "        # Calculate hidden state\n",
    "        h_prev = o * tanh(C_prev)\n",
    "        h_s.append(h_prev)\n",
    "\n",
    "        # Calculate logits\n",
    "        v = np.dot(W_v, h_prev) + b_v\n",
    "        v_s.append(v)\n",
    "        \n",
    "        # Calculate softmax\n",
    "        output = softmax(v)\n",
    "        output_s.append(output)\n",
    "\n",
    "    return z_s, f_s, i_s, g_s, C_s, o_s, h_s, v_s, output_s\n",
    "\n",
    "\n",
    "# Get first sentence in test set\n",
    "inputs, targets = test_set[1]\n",
    "\n",
    "# One-hot encode input and target sequence\n",
    "inputs_one_hot = one_hot_encode_sequence(inputs, vocab_size)\n",
    "targets_one_hot = one_hot_encode_sequence(targets, vocab_size)\n",
    "\n",
    "# Initialize hidden state as zeros\n",
    "h = np.zeros((hidden_size, 1))\n",
    "c = np.zeros((hidden_size, 1))\n",
    "\n",
    "# Forward pass\n",
    "z_s, f_s, i_s, g_s, C_s, o_s, h_s, v_s, outputs = forward(inputs_one_hot, h, c, params)\n",
    "\n",
    "output_sentence = [idx_to_word[np.argmax(output)] for output in outputs]\n",
    "print('Input sentence:')\n",
    "print(inputs)\n",
    "\n",
    "print('\\nTarget sequence:')\n",
    "print(targets)\n",
    "\n",
    "print('\\nPredicted sequence:')\n",
    "print([idx_to_word[np.argmax(output)] for output in outputs])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 反向传播"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We get a loss of:\n",
      "4.940597374930116\n"
     ]
    }
   ],
   "source": [
    "def backward(z, f, i, g, C, o, h, v, outputs, targets, p = params):\n",
    "    \"\"\"\n",
    "    Arguments:\n",
    "    z -- your concatenated input data  as a list of size m.\n",
    "    f -- your forget gate computations as a list of size m.\n",
    "    i -- your input gate computations as a list of size m.\n",
    "    g -- your candidate computations as a list of size m.\n",
    "    C -- your Cell states as a list of size m+1.\n",
    "    o -- your output gate computations as a list of size m.\n",
    "    h -- your Hidden state computations as a list of size m+1.\n",
    "    v -- your logit computations as a list of size m.\n",
    "    outputs -- your outputs as a list of size m.\n",
    "    targets -- your targets as a list of size m.\n",
    "    p -- python list containing:\n",
    "                        W_f -- Weight matrix of the forget gate, numpy array of shape (n_a, n_a + n_x)\n",
    "                        b_f -- Bias of the forget gate, numpy array of shape (n_a, 1)\n",
    "                        W_i -- Weight matrix of the update gate, numpy array of shape (n_a, n_a + n_x)\n",
    "                        b_i -- Bias of the update gate, numpy array of shape (n_a, 1)\n",
    "                        W_g -- Weight matrix of the first \"tanh\", numpy array of shape (n_a, n_a + n_x)\n",
    "                        b_g --  Bias of the first \"tanh\", numpy array of shape (n_a, 1)\n",
    "                        W_o -- Weight matrix of the output gate, numpy array of shape (n_a, n_a + n_x)\n",
    "                        b_o --  Bias of the output gate, numpy array of shape (n_a, 1)\n",
    "                        W_v -- Weight matrix relating the hidden-state to the output, numpy array of shape (n_v, n_a)\n",
    "                        b_v -- Bias relating the hidden-state to the output, numpy array of shape (n_v, 1)\n",
    "    Returns:\n",
    "    loss -- crossentropy loss for all elements in output\n",
    "    grads -- lists of gradients of every element in p\n",
    "    \"\"\"\n",
    "\n",
    "    # Unpack parameters\n",
    "    W_f, W_i, W_g, W_o, W_v, b_f, b_i, b_g, b_o, b_v = p\n",
    "\n",
    "    # Initialize gradients as zero\n",
    "    W_f_d = np.zeros_like(W_f)\n",
    "    b_f_d = np.zeros_like(b_f)\n",
    "\n",
    "    W_i_d = np.zeros_like(W_i)\n",
    "    b_i_d = np.zeros_like(b_i)\n",
    "\n",
    "    W_g_d = np.zeros_like(W_g)\n",
    "    b_g_d = np.zeros_like(b_g)\n",
    "\n",
    "    W_o_d = np.zeros_like(W_o)\n",
    "    b_o_d = np.zeros_like(b_o)\n",
    "\n",
    "    W_v_d = np.zeros_like(W_v)\n",
    "    b_v_d = np.zeros_like(b_v)\n",
    "    \n",
    "    # Set the next cell and hidden state equal to zero\n",
    "    dh_next = np.zeros_like(h[0])\n",
    "    dC_next = np.zeros_like(C[0])\n",
    "        \n",
    "    # Track loss\n",
    "    loss = 0\n",
    "    \n",
    "    for t in reversed(range(len(outputs))):\n",
    "        \n",
    "        # Compute the cross entropy\n",
    "        loss += -np.mean(np.log(outputs[t]) * targets[t])\n",
    "        # Get the previous hidden cell state\n",
    "        C_prev= C[t-1]\n",
    "        \n",
    "        # Compute the derivative of the relation of the hidden-state to the output gate\n",
    "        dv = np.copy(outputs[t])\n",
    "        dv[np.argmax(targets[t])] -= 1\n",
    "\n",
    "        # Update the gradient of the relation of the hidden-state to the output gate\n",
    "        W_v_d += np.dot(dv, h[t].T)\n",
    "        b_v_d += dv\n",
    "\n",
    "        # Compute the derivative of the hidden state and output gate\n",
    "        dh = np.dot(W_v.T, dv)        \n",
    "        dh += dh_next\n",
    "        do = dh * tanh(C[t])\n",
    "        do = sigmoid(o[t], derivative=True)*do\n",
    "        \n",
    "        # Update the gradients with respect to the output gate\n",
    "        W_o_d += np.dot(do, z[t].T)\n",
    "        b_o_d += do\n",
    "\n",
    "        # Compute the derivative of the cell state and candidate g\n",
    "        dC = np.copy(dC_next)\n",
    "        dC += dh * o[t] * tanh(tanh(C[t]), derivative=True)\n",
    "        dg = dC * i[t]\n",
    "        dg = tanh(g[t], derivative=True) * dg\n",
    "        \n",
    "        # Update the gradients with respect to the candidate\n",
    "        W_g_d += np.dot(dg, z[t].T)\n",
    "        b_g_d += dg\n",
    "\n",
    "        # Compute the derivative of the input gate and update its gradients\n",
    "        di = dC * g[t]\n",
    "        di = sigmoid(i[t], True) * di\n",
    "        W_i_d += np.dot(di, z[t].T)\n",
    "        b_i_d += di\n",
    "\n",
    "        # Compute the derivative of the forget gate and update its gradients\n",
    "        df = dC * C_prev\n",
    "        df = sigmoid(f[t]) * df\n",
    "        W_f_d += np.dot(df, z[t].T)\n",
    "        b_f_d += df\n",
    "\n",
    "        # Compute the derivative of the input and update the gradients of the previous hidden and cell state\n",
    "        dz = (np.dot(W_f.T, df)\n",
    "             + np.dot(W_i.T, di)\n",
    "             + np.dot(W_g.T, dg)\n",
    "             + np.dot(W_o.T, do))\n",
    "        dh_prev = dz[:hidden_size, :]\n",
    "        dC_prev = f[t] * dC\n",
    "        \n",
    "    grads= W_f_d, W_i_d, W_g_d, W_o_d, W_v_d, b_f_d, b_i_d, b_g_d, b_o_d, b_v_d\n",
    "    \n",
    "    # Clip gradients\n",
    "    grads = clip_gradient_norm(grads)\n",
    "    \n",
    "    return loss, grads\n",
    "\n",
    "\n",
    "# Perform a backward pass\n",
    "loss, grads = backward(z_s, f_s, i_s, g_s, C_s, o_s, h_s, v_s, outputs, targets_one_hot, params)\n",
    "\n",
    "print('We get a loss of:')\n",
    "print(loss)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 训练模型"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epoch 0, training loss: 2.9126594208151486, validation loss: 3.7627056786333304\n",
      "Epoch 5, training loss: 1.2746721453770284, validation loss: 1.3007947595266\n",
      "Epoch 10, training loss: 1.1492599735091495, validation loss: 1.1397926520784123\n",
      "Epoch 15, training loss: 0.9836092135358966, validation loss: 0.9939491353315226\n",
      "Epoch 20, training loss: 0.8791899647621022, validation loss: 0.8975219678277732\n",
      "Epoch 25, training loss: 0.8008628436073784, validation loss: 0.8188702401659993\n",
      "Epoch 30, training loss: 0.754772129866406, validation loss: 0.759879234320202\n",
      "Epoch 35, training loss: 0.7316903442197213, validation loss: 0.7280875207336993\n",
      "Epoch 40, training loss: 0.7181688528186634, validation loss: 0.7100343175260162\n",
      "Epoch 45, training loss: 0.7091859818959982, validation loss: 0.69897796740037\n",
      "Input sentence:\n",
      "['a', 'a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b']\n",
      "\n",
      "Target sequence:\n",
      "['a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'EOS']\n",
      "\n",
      "Predicted sequence:\n",
      "['a', 'a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'EOS']\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX8AAAECCAYAAAAW+Nd4AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nO3de3wV5b3v8c8vWQkr3EII0SDhDiKBoij35FTAchO8Y+u1Ra1W21OPW6ttdXeX3W6t1NZja91WrRzdaNtdt5YCVkFEaokg4AXkKhe5BARDkJCE3POcP2YlhBAgkLWykjXf9+s1rzVr8qzJb8iL78x6ZuYZc84hIiL+EhftAkREpPkp/EVEfEjhLyLiQwp/EREfUviLiPhQINoFNEaXLl1cr169ol2GiEir8sEHHxxwzqU19LNWEf69evVi9erV0S5DRKRVMbOdJ/qZun1ERHxI4S8i4kMKfxERH2oVff4i0jwqKirIzc2ltLQ02qXIaQgGg2RkZJCQkNDozyj8RaRWbm4uHTp0oFevXphZtMuRRnDOkZ+fT25uLr17927059TtIyK1SktLSU1NVfC3ImZGamrqaX9bU/iLyDEU/K3PmfzNYjr8162Df/1XyM+PdiUiIi1LTIf/li3w8MOwe3e0KxGRxvjtb39LdnY2SUlJZGdn89prr53W5z/66CNmz559ynb79u3jkUceOdMyGzR27Niwri/SYvqEb+fO3uvBg9GtQ0Qa5+677+buu++mX79+LFu27LQ/P3ToUIYOHXrKdunp6Tz44INnUmLMUPiLSMPuuQc+/ji867zgAnjiidP6yI4dO3jooYdISkqiurqa2bNns379embMmEFcXBwzZszgrrvuAmDp0qUsXbqUmTNnAt7R+NSpU3nllVdIT09n3rx5teucOXMmL7zwAgAzZsygb9++/P3vf8fMWLJkCQUFBVxzzTWUlZUxaNAgsrKyuP322xtV88GDB/nmN79Jfn4+I0eO5IknniAvL4+vf/3rlJSUMHToUJ5++ukGlzWXmO72UfiLxIb58+fz7W9/u7ZLZ8+ePTz//PMsWLDglN08wWCQlStXUlhYyN69e0/Y7tChQyxfvpwBAwbw4Ycf8t577zFlyhTmzp1Lfn5+o4Mf4JFHHuEb3/gGy5cv58svv2ThwoW8++67DB48mBUrVpCVlUV1dXWDy5qLL478dcJX5Ayc5hF6JE2cOJFRo0bVvo+Pj+fBBx+kS5cuVFZWnvSzt9xyCwA9e/akvLy80e369u3Lz3/+c954443abxKNtWHDBu68804ARo8ezYYNG/jOd77D0qVLmTZtGsOHDycuLo4pU6Yct6y5xPSRf1KSN+nIX6R1a9++/THvZ86cyTPPPMOjjz5KVVXVaX22se3mzp3L888/z7Jly/ja1752WvUOGjSIFStWALBixQoGDRpETk4O119/PQsWLGDRokVs27atwWXNJaaP/ME7+lf4i8SWq6++mkmTJtGnTx8qKyspLS0lGAyG9XdcdNFFXHHFFfTp04eMjAxmzZpFt27dGvXZH//4x9x888089dRTjBw5kokTJ7Jjxw5uuukmysrKyMjIoGfPnsTHxx+3rLmYc67ZftmZGjZsmDvT8fyHDIG+feGvfw1zUSIxaOPGjQwcODDaZbQIM2fO5J133iExMZFgMMijjz7KoEGDol3WCTX0tzOzD5xzwxpqryN/EZEGzJw587T7+luTmO7zB0hN1QlfEZH6Yj78deQvInI834R/Kzi1ISLSbHwR/mVlUFIS7UpERFoOX4Q/qOtHpDW45JJL+OijjwB4++23ufbaa0/avqHB1L7//e832HbGjBns2LHjhOuqGeqhrsYOFNdYO3bsYMaMGWFbX1OEPfzNLGBmr5hZjpk1+K9mZsPNLNfMloWmAeGuo0Zqqveqk74iLd/kyZN5++23AVi8eDGTJk067XU8+eSTZ/S7Gwr/oUOHcuutt57R+lq6SBz5Xwmscc5lAV3N7IIG2qQATzvnskPT5gjUAejIX+RM3XMPjB0b3umee07+OydNmsTixYsB78h/0qRJFBcXM2XKFEaPHl07BMPJ1P02sHPnTsaMGcMll1zCpk2bAFi/fj3Dhw9n5MiRPP300xQUFJCdnc1HH31EdnY2s2bNqv183UHiAD788EPGjBnD8OHDefnll2t/32OPPcaIESO4/PLLT1lfXZ999hnjxo1jxIgRPPbYYwBs3ryZrKwshg8fzsMPP3zCZU0VifB/E3jczAJAJ+BwA21SgGvMbKWZvWoRfHSQwl+k9RgyZAjbtm1j3759lJaW0r17d/bs2cNdd93FO++8w/bt29m/f3+j1zdr1izuv/9+3nzzTQ4dOgQcPyhccnIyy5YtY+jQoSxbtowf/vCHJ1zf9773PV566SWWLVvGL3/5y9p1NnbwuPruv/9+fvazn7FixQreeOMNNm7cyIIFC7j66qtZtWoVPXr0AGhwWVOF/SYv51wRgJm9D3zunNveQLOtwE+cc6+b2XvAxcDSug3M7A7gDqBJG6vwFzkz0RrXLTs7m4cffrh2PJ1gMMicOXOYM2cOhw4douQ0rt7Yvn07559/PgkJCbXj/J/OoHD15efn06dPHwAGDhzIZ599BjR+8Lj6Nm7cyOjRo4mLi2PEiBFs2rSJm2++mR/96EdMmzaNqVOnAjS4rKki0eefamZtgDFAipmNa6DZDmBxnfmz6jdwzj3rnBvmnBuWlpZ2xvUo/EVal8mTJ/P73/+eyZMnA/Dcc89x5ZVX8sc//pF27dqd1rp69OjBunXrqKysZO3atcCJB4VLSkqiuLiYkw1506VLF3bs2EF5eTmbNm2id+/eQOMHj6svMzOTFStW4Jxj1apVDBw4kCVLlvCjH/2IefPmMWvWLCoqKhpc1lSRGN7hPmCDc+4lMzsCJDXQ5l7gUzObAwwG/iMCdQDQti0EgzrhK9JaTJgwgTZt2vDVr3619v2dd97JM888g5mxd+9eevXq1ah1PfDAA9x44438+te/rh347USDwt1xxx2MHz+ejh078tZbbzW4vieffJIbbriBiooK7r//fjp16tSkbf3lL3/JrbfeSnFxMddeey3nnXceRUVF3HzzzVRWVjJ58mQSEhLo16/fccuaKuwDu5lZN2AOXuhvA34K3OWc+0GdNl2BPwHtgL875356snU2ZWA3gG7dYMoU+MMfzngVIr6ggd1ar6gP7Oac2wOMr7f4B/XafA6MDffvPhEN8SAicqyYv8kLFP4ip6M1DPMuxzqTv5nCX0RqBYNB8vPztQNoRZxz5Ofnn/bDbGJ+PH/w7vJduTLaVYi0fBkZGeTm5pKXlxftUuQ0BINBMjIyTuszvgh/HfmLNE5CQkLt5YsS23zT7VNaqpE9RURq+Cb8QUf/IiI1fBH+GtlTRORYvgh/HfmLiBxL4S8i4kMKfxERH1L4i4j4kC/Cv21baNNGJ3xFRGr4IvzNdKOXiEhdvgh/UPiLiNSl8BcR8SGFv4iID/km/FNTdcJXRKSGb8JfR/4iIkf5KvxLSjSyp4gI+Cz8Ab78Mrp1iIi0BL4Lf3X9iIj4KPw1rLOIyFG+CX8d+YuIHKXwFxHxIYW/iIgPhT38zSxgZq+YWY6ZzT5Bm6CZLTCzNWY2x8ws3HXU164dJCQo/EVEIDJH/lcCa5xzWUBXM7uggTY3AbnOufOBFGBCBOo4hpnu8hURqRGJ8H8TeNzMAkAn4HADbcYDb4XmlwDj6jcwszvMbLWZrc7LywtLYbrLV0TEE/bwd84VOeeOADnAfufc9gaapQIFofnDQOcG1vOsc26Yc25YWlpaWGpT+IuIeCLR559qZm2AMUCKmR13VA8cAJJD88mh9xGn8BcR8USi2+c+4FrnXBVwBEhqoM3bwMTQ/HjgnQjUcRyFv4iIJxLh/xRwq5ktB/KBzWb2q3ptXga6mdla4CDeziDidMJXRMQTCPcKnXN78I7m6/pBvTZlwLRw/+7jLF4MDz4Ir70GGRl07gxHjkBpKQSDEf/tIiItVmzf5FVVBatWwc6dgEb2FBGpEdvh372797prF6C7fEVEavgj/HfvBhT+IiI1Yjv8O3SA5OTa8NewziIintgOf4AePXTkLyJST+yHf/fu6vMXEanHH+EfOvJv3x4CAYW/iIg/wv/AASgpwUx3+YqIgF/CHyA3F9BdviIi4Ifw79HDe63T768jfxHxu9gP/wau9Vf4i4jfxX74Z2R4rwp/EZFasR/+bdrAWWcdc6OXwl9E/C72wx+8fv86ff5FRVBeHuWaRESiyB/hX+daf93oJSKi8BcR8SX/hH9hIRQUKPxFRPBT+APs2lU7sqfCX0T8zB/hX3Oj1+7dtUf+ustXRPzMH+Ff50YvdfuIiPgl/Lt2hfh42L2bDh28WYW/iPiZP8I/Ph7OOQd27dLIniIi+CX84ZgneukuXxHxO/+Ef71r/XXCV0T8LCLhb2YvmtkKM5tnZoEGfj7czHLNbFloGhCJOo7Rvbs3pn91tbp9RMT3wh7+ZpYNBJxzo4COwMQGmqUATzvnskPT5nDXcZzu3aGsDPLyFP4i4nuROPLfD/zmFOtPAa4xs5Vm9qqZWQTqOFa9yz0V/iLiZ2EPf+fcFufcSjO7CqgGFjXQbCvwE+fcCKArcHH9BmZ2h5mtNrPVeXl5TS+szo1eqaneaA8VFU1frYhIaxSpPv/LgbuBy5xzlQ002QEsrjN/Vv0GzrlnnXPDnHPD0tLSml6UbvQSEakViT7/dOB+YJpzrvAEze4FrjOzOGAwsC7cdRynSxcIBmHXLoW/iPheJI78v4XXlbMwdCXPbWb2q3ptfgfcArwP/NU5tyECdRzLzHuko478RUQ47jLMpnLOzQJmnaLN58DYcP/uUwrd6KXwFxG/889NXlB7o1eXLt7bL76IbjkiItHiv/Dfu5eM9EoSE+HTT6NdkIhIdPgv/KurCXyxlwEDYEPkzzSIiLRI/gt/gN27ycxU+IuIf/kr/Ovc6DVwIHz2GZSURLckEZFo8Ff41zvydw42R35UIRGRFsdf4d+xozft2kVmprdIXT8i4kdnFP5m9t1wF9JsQpd79u/vPeBL4S8ifnSmR/4zwllEswrd6JWYCP37w8aN0S5IRKT5+avbB455otfAgTryFxF/OunwDmZ2Q0OLgc6RKacZdO8OeXlQUkJmZhLz5kF5OSQmRrswEZHmc6qxffqfYPmccBfSbGqu+MnNJTOzP1VVsGULDBoU3bJERJrTScPfOffvDS1v9Sd8IXS5p7dv27BB4S8i/uLPE74Au3czYIA30rNO+oqI3/jvhG9Ghve6axdJSdCnj076ioj/+O+EbzAIaWm64kdEfK0xJ3xdaN7qzP9XxCpqDnUu98zMhEWLoLISAmF/tI2ISMvUmG4f42jwjwNmEo2ncIVT6EYv8MK/vBy2b49yTSIizeik4R+62ucXwG5gKrALuNA5N74Zaouc7t1h1y6A2jF+dNJXRPzkpOFvZg/jBf+NeM/lfQZoa2ZjmqG2yOneHQoLoaCA887zFqnfX0T85FS93OcAfw/NX1ZnuQPei0hFzaHOtf4dBifTvbvCX0T85VQ3ed3SXIU0qzrhz+DBeqqXiPiO/67zB+/ifqh9kktmptfnX10dxZpERJqRP8O/a1fv6H/5csAL/5KS2nPAIiIxLyLhb2YvmtkKM5tnZsd1LZlZ0MwWmNkaM5tjZhaJOk4qKwtycsA5PdVLRHwn7OFvZtlAwDk3CugITGyg2U1ArnPufCAFmBDuOk4pKwv27IFduxg40Fuk8BcRv4jEkf9+4DenWP944K3Q/BK8m8eaV1aW95qTQ0oKpKcr/EXEP8Ie/s65Lc65lWZ2FVANLGqgWSpQEJo/TANjBZnZHWa22sxW5+XlhbtM+MpXoH17r+sHdMWPiPhKpPr8LwfuBi5zzlU20OQAkByaTw69P4Zz7lnn3DDn3LC0tLTwFxkIwMiR8J53u0LNFT/OneJzIiIxIBJ9/unA/cA051zhCZq9zdFzAeOBd8JdR6NkZcHatVBYSGYmHD4Me/dGpRIRkWYViSP/bwFdgYVmtszMbjOzX9Vr8zLQzczWAgfxdgbNLyvLu7h/xQqd9BURXwn7IMbOuVl44wCdrE0ZMC3cv/u0jRoFcXGQk0Pmd70LjjZsgAnNf+2RiEiz8udNXjU6dvRO/ObkkJYGqak68hcRf/B3+AOMGQMrVmDVVbUnfUVEYp3CPysLiorgk0/IzIT163XFj4jEPoV/nZu9Bg6EgwchErcViIi0JAr/nj3hnHO8k74a40dEfELhb1Y7yJvCX0T8QuEP3knfXbs4pzqX5GT4+ONoFyQiElkKf6jt97fl7zFhAsyfD1VVUa5JRCSCFP4AF1wAbdtCTg7Tp8O+fbVD/oiIxCSFP0BCAowYATk5XHopBIPw6qvRLkpEJHIU/jWysuDjj+lgRUya5IW/nukrIrFK4V8jK8vr6F+1iunTITcXVq6MdlEiIpGh8K8xapT3mpPDZZd5PUH/8z/RLUlEJFIU/jVSUmDQIMjJITnZG9nz1Vc11IOIxCaFf11ZWbB8OVRXM3067NgBH34Y7aJERMJP4V9XVhYUFMD69VxxhfekR3X9iEgsUvjXVWeQt86dYdw4L/zV9SMisUbhX1efPtCtG8ydC8D06bB1K3zySZTrEhEJM4V/XWbw3e/CwoWwZg1XXuk95VFdPyISaxT+9d11F7RvD489xllnwVe/qvAXkdij8K8vJQXuuAP+/GfYsYPp071HO2qYZxGJJQr/hvzLv3hdQI8/zlVXebMa60dEYonCvyEZGXDjjfCHP3BO4gHGjFHXj4jEFoX/iTzwAJSUwFNPMX06rF0LW7ZEuygRkfCISPibWYKZzT/Jz4ebWa6ZLQtNAyJRR5NkZsJll8GTT3L15COAun5EJHaEPfzNLAn4AJhwkmYpwNPOuezQtDncdYTFAw9Afj49Fs9m5Eh4/nnvy4CISGsX9vB3zpU454YAuSdplgJcY2YrzexVM7Nw1xEW2dne831//Wt+9tMqtm6Fn/wk2kWJiDRdtPr8twI/cc6NALoCF9dvYGZ3mNlqM1udl5fX7AXW+uEPYccOJn7539x5Jzz+OPzzn9ErR0QkHMxFaOAaM9vqnOt3gp+lAkXOuTIz+yMw1zn3lxOta9iwYW716tURqfOUqqth8GBITKTonx9x/gXel5Q1a7x7wUREWioz+8A5N6yhn0XryP9e4DoziwMGA+uiVMepxcXB/ffDmjW0f28RL7wAn33mnQ4QEWmtIh7+ZtbbzH5Vb/HvgFuA94G/Ouda9v2zN97oDfj20EP8r2El3HsvPP00LFoU7cJERM5MxLp9wimq3T41XnvNG+Zz2jRK//gaF44IUFjojfjZqVN0SxMRaUhL7PZpfa6+Gn73O5g/n+D/+Q4vvuD4/HO4555oFyYicvoU/qfju9+Ff/s3mD2b4XMf4sEH4cUX4W9/i3ZhIiKnR+F/umbO9Eb9/MUv+NfkJ7ngArjtNnjvvWgXJiLSeAr/02UG//mfcPXVJP7gbv5y83w6dYKxY+G556JdnIhI4yj8z0R8PLz8Mlx8Mf1/dA2rZi1h/HjvC8Fdd0F5ebQLFBE5OYX/mQoGvc7+zExSbryU10f9nB/+oJLf/x7Gj4d9+6JdoIjIiSn8myI5Gd56C668kvh//zcenTeIPz20jg8/hGHDYNWqaBcoItIwhX9TpaV5j3xcuBCqqrju4a/w3sU/JiGukuxs76Fg+hYgIi2Nwj9cJk6Edevgpz/lgiWPs+rQudx44QaefNLRpw/cdx/s3x/tIkVEPAr/cAoGvUtBP/mELiP7MnvFIDa1vYiv91jOE084+vRxPPAARHOQUhERUPhHxrnnegP/vP02/S7P5IWd49lYPYCrExbw619V07tXNbffDu++6w0aKiLS3BT+kWLmXfbz0kuwbx/n/v4+5pz3MOtdJteWzOFPs0u4+GLo062Mh35czaZN0S5YRPxEA7s1tw0bYM4civ/+D+au7c1L3MQiJlJNPMN6fMG10x1TZ6SROTiOFvp8MxFpJU42sJvCP5ry8mDJEvb97X3+9EYnXjo0lQ+5CIBewX1cOmgnU6cZ427rQ1L3LlEuVkRaG4V/a+AcbN3K7vkf88bfynn9424sPjycI7QjiSOMbbuS8efmcsk4x/lX9CJu2IXQrl20qxaRFkzh30qV5hfz7gvbef21MhZ9ks6mwgwAOpPPOJYyvutGxo8uYcCUPljWGBgwwHvymIgICv+YsWcPLPlrAUvmHubtVR3Yfdh7ikw6nzOWpYxNWsnYYUWcO6GntzMYPRqSkqJctYhEi8I/BjkH27bB24sd/3i9kKXLAnx+qC0AXdnLWJYyLrCMcSOK6Xv5IGziBDj/fH0zEPERhb8POAdbtsDSpfCPt8p4Z4nj84NBALqzi3G8w/gOqxk31tHj+iyYOhU6doxu0SISUQp/H3IOPv0UliyBJa+XsPRd40ChtzM4l81MilvMpGH5XHxbP9pfOwVSUqJcsYiEm8JfqK72hh5a8nY1i/5yiKWr21NSmUgC5WRbDpP6f8alN6cy+J6vYe11FZFILFD4y3FKS2HZu9Us/K99LFxofHKgKwC9bAdXDNzC5d/pyv+6cxAJibrTTKS1UvjLKe3d43j9N1v525+OsDh3AGUE6RRXwNQhu7nizq5celOqbisQaWUU/nJaivcXseg/VjLvlTIW7B/GAdJoG1/KtFH5XPv9dC69LJ62baNdpYicysnCPyLX/ZlZgpnNP8nPg2a2wMzWmNkcM41i05K0O7s9Vz05nv+3bwr7NhXwzo1/4Ftt/szSnADXXhdPWqdyrptWyKuvQklJtKsVkTMR9vA3syTgA2DCSZrdBOQ6584HUk7RVqIofkA/xr70bf6z4Cb2vvY+S0Y9yDcrZrPk9RKmT4e0lApumF7O3LneeQQRaR3CHv7OuRLn3BAg9yTNxgNvheaXAOPCXYeEWSBA/FWXM275Izydexl7Zz7H4q43c2PZbBa9epirroKzOldw8/WVzJ+vbwQiLV20bvdMBQpC84eBzvUbmNkdZrbazFbn6dFXLUu3bgR++hCX7Pkvnnl/KJ9//xcs7Hw9Xy95kdf/fJjLL4fUTpVcPqWcZ5/1hqUQkZYlYid8zWyrc67fCX72MvCac+5VM7sP6Oyce+hE69IJ31agqgrefZeKl/6bJX85wIKii5nPZeykFwBDBxQz7dq2fG2CMXy4hhwSaQ5RudrnFOF/KzDSOfcdM3sd+L/OucUnWpfCv5WprISVK3FvvMmGuZ+yYF0vFjCV9xhDNfEkxFdxUWYJ2RPakv3VOLKyoIseVyASdlENfzPrDXzPOfeDOj9rA7wK9ADWAN90JylE4d/K5eXBW29x8G//JOedcpblnUsOWaxiOOW0AaBv1yMMuTCer1zUhiFDYMgQ6NMH4uOjXLtIK6br/KVlyc2FnBxKl65g9eJD5Gw9mw+4kLUMYQv9qcZL/LbBKjIHOs4dGGDAADj33KNT+/ZR3gaRVkDhLy3b4cOwejWsXk3J+2vYsPwwaz/vwlqGsJ5BfBrIZFflObg61yd07ero39/o14/jpg4dorgtIi2Iwl9anwMH4IMPvGnNGko+3MjWrfAp/fmUc/k0cTBbg4PZWtmLfUeSj/loevqx3xJqpr59ITExStsjEgUKf4kNRUXwySewZg18/LE3v24dRYer2EZfttKPLcnD2dLhQm8ncTidLw4fvawoPt7bAQwcePykbiSJRQp/iV3Owa5d3o6gZlq3DjZtgooKCujIlrjz2Jx+MZuSR7LRBrLhcAZb9nWgsvLoqCK9esHgwTBokPc6eDCcdx4Eg9HbNJGmUviL/1RUeE+zWbfOm2p2Ctu3g3NUEGBbYiYbuk1gQ8dRrCeTdYcy2Ly3AxUV3k4hLg769z9+p9C/PwQCUd4+kUZQ+IvUKC6GjRuP3SmsX197G3IFAbYEh7D+nK/xSfvRrK8ayLovz2HrvvZUV3s7hcREGDAAMjOPnfr10zkFaVkU/iKncugQbNjg7QjWrz86v3cvAKW0YVP8YNaljeOT9qPZ6AawviCDz/I74py3UwgEvHsTBgzwpvPOOzrfpQto7Fppbgp/kTN1+DBs3uydQ6g7bdsGZWUcIYnNDGB94AI2JI9mc8IgNpf3ZkvBWZRXHe0bSk529O1r9O3LMVOfPtCtm7qRJDIU/iLhVl3t3ay2das3bdnive7YAZ99RlVBITvpyWYGsJkBbI0/j21tMtnmerOjrCsV1UfTPj7e0e3sKnr2Nnr2jqdnT+jZEzIyvB1DRgakpOibg5w+hb9Iczt0yNsRhHYG5ObWTlW797J7bzzbqnqynT7spOfRyXqzx3WlimO/CgQTKunWuYSMsyvomg7p3eJJ75lIes8g6V2Ns8+Gs86CtDRISIjKFksLpPAXaWmqq+GLL7wTzfv3w759tVPl3i/Yu6uSPV8ksOdgErmFyezhHHLJYA/d2Ec6+0inkI4NrrpTQhFpScWc1eEIaR3L6NKpitSUajqnQmqXOFLTE+icnkjnc4KknJNESkY7kjoE9M0iBp0s/NXTKBINcXHercjp6cf9KIA34mGPmgVVVfDll95dz3l58OUmOPgexZ8fZl9uJfv2VvP5F/HkfRkgrzBIXlESeaUdyPu8I9v2pPI+XcgntXYQvYYkUE6KHSIlvpBOCUUkJ5TQsU0pycEykpPK6di2iuT2lXRoV03HDo4O7aFDcpw3dYqnQ0qAdskBgsltsKSgN2Z3sM5rzZSYqP6rFkLhL9LSxcd7lwt16eJdQhTSDugbmk6ovBwKC3EFeyneX8TBvaXk7y0jf18FB/OqOHQIvjxkfHk4nkNFAb4sTuDQkTYUlHViV1EShw8lUVDZjmLXrlGlxlFFe4poR3Ho9SBtOUI7imlHsTcfV0rbQDltA+UkBSpISqikbWIFSYlVJCVWk9SmmmBiNUlB580nGUlBRzAIbZLiCCYZwSQjEAxgbRK9HUpCwtHX+vMNvU9I8M6yn2i+5n0g4P37x+AOS+EvEssSEyE1FUtNpX0faE+dbxSnoeM4yUoAAAWfSURBVLLSu/CpsBAKC6opzC/3poMVFB6soKigkqLD1RQddhQXOYqKoKi4DcVHghwpTaOwNI79ZfEUlwU4Up5AcUUCJaUJx5z4Pl1xVNGGspNOiZSHXktowyESKW9wSqDiuNdj5uOqSYivJhDvSIj35hMCjoSA85bVvNbsR+KrCSSYNx9wBBKs9jUQAEsI7VQC9V7rTjXLLrkEpk4943+nE1H4i8gpBQLQubM3eU9/DYampqms9J73XFICR454U2mpN5WUHH0tKYGysqM/KyuD0pI4SorbUF6aQFlJW8pKqykrcZSVOsrKHGWl3hefQ+VQVg7l5UZZuVFWYVRUelN5ZVxoOsWDI6pDU0WTNxnwdlwBqyKeKgJUEbBKAniTtyw076q4Y9127g1/9iv8RSR6AgFvCO4zG4bbgPjQ1DTOeTuiigpvKi9veL5um7rv67/WzNdMdX9WVQWVlfGhyXt/dDm1y2rmz7783CZvX0MU/iLie2ZHu/z9Iu7UTUREJNYo/EVEfEjhLyLiQwp/EREfUviLiPiQwl9ExIcU/iIiPqTwFxHxoVYxpLOZ5QE7z/DjXYADYSynNfHrtmu7/UXbfWI9nXNpDf2gVYR/U5jZ6hONZx3r/Lrt2m5/0XafGXX7iIj4kMJfRMSH/BD+z0a7gCjy67Zru/1F230GYr7PX0REjueHI38REalH4S8i4kMxG/5mFjSzBWa2xszmmMXgE5jrMbMEM5sfmvfN9pvZi2a2wszmmVl7P2y3mQXM7BUzyzGz2X76ewOY2b1mttjMupjZP83sEzN7NNp1RYqZDTezXDNbFprOb+rfO2bDH7gJyHXOnQ+kABOiXE9EmVkS8AFHt9MX229m2UDAOTcK6Ajcig+2G7gSWOOcywK6Av8bf2w3ZtYT+Fbo7T3A68D5wBQzi8wzD6MvBXjaOZftnMsGhtPEv3csh/944K3Q/BJgXBRriTjnXIlzbgiQG1rkl+3fD/wmNB8HzMQf2/0m8LiZBYBOwIX4Y7vB+3v/ODQ/HnjLOVcN/IPY3e4U4BozW2lmrwKX0MS/dyyHfypQEJo/DHSOYi3R4Ivtd85tcc6tNLOrgGrgI/yx3UXOuSNADt4O0Bd/bzO7AVgDbAgt8sV2A1uBnzjnRuB907uaJm53LIf/ASA5NJ+M/8b+8M32m9nlwN3AZcA+fLDdZpZqZm2AMXhHhYPxwXYD0/COev8MXIQ3vo0ftnsHsLjOfDVN3O5YDv+3gYmh+fHAO1GsJRp8sf1mlg7cD0xzzhXik+0G7gOudc5VAUeAh/HBdjvnbgj1eV+Hd47rKWCimcUBFxOj2w3cC1wX2s7BeH//Jv29Yzn8Xwa6mdla4CBeKPiJX7b/W3hfgxea2TIgAX9s91PArWa2HMgHnscf213fb4FLgbXA6865rVGuJ1J+B9wCvA/8lTD8vXWHr4iID8Xykb+IiJyAwl9ExIcU/iIiPqTwFxHxIYW/SD1mNsPMdtYZR2VKE9c1I4zliYRFINoFiLRQzznn/iPaRYhEisJf5BTMbCYwAu9Oyj3A9Xj/d14AegA7gRl436RfAHoCecA3Qqv4ipn9AzgLmO6cW99sxYucgLp9RBp2m5ktNbOlQDfgvdAImvnAFcDtwIbQsi14N+DcgTfS5mhgHjAktK7ReKMuPhr6rEjUKfxFGva8c26sc24s3tH+qtDyj4HeQCawPLRseej9ecDK0LLZwOrQ/B+dc+V43xASI1+6yKkp/EUaZ2To9UJgG7AeGBVaNir0flOddg/hfRsAKGqmGkUaTX3+Ig273cwmh+a/AvwjNHZQLjCfUJ+/meXgHdE/AsQDL4bafQE8hjcAmUiLo7F9RE4hdMJ3qXNuaZRLEQkbhb+IiA+pz19ExIcU/iIiPqTwFxHxIYW/iIgPKfxFRHzo/wP9xEveM06mHQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Hyper-parameters\n",
    "num_epochs = 50\n",
    "\n",
    "# Initialize a new network\n",
    "z_size = hidden_size + vocab_size # Size of concatenated hidden + input vector\n",
    "params = init_lstm(hidden_size=hidden_size, vocab_size=vocab_size, z_size=z_size)\n",
    "\n",
    "# Initialize hidden state as zeros\n",
    "hidden_state = np.zeros((hidden_size, 1))\n",
    "\n",
    "# Track loss\n",
    "training_loss, validation_loss = [], []\n",
    "\n",
    "# For each epoch\n",
    "for i in range(num_epochs):\n",
    "    \n",
    "    # Track loss\n",
    "    epoch_training_loss = 0\n",
    "    epoch_validation_loss = 0\n",
    "    \n",
    "    # For each sentence in validation set\n",
    "    for inputs, targets in validation_set:\n",
    "        \n",
    "        # One-hot encode input and target sequence\n",
    "        inputs_one_hot = one_hot_encode_sequence(inputs, vocab_size)\n",
    "        targets_one_hot = one_hot_encode_sequence(targets, vocab_size)\n",
    "\n",
    "        # Initialize hidden state and cell state as zeros\n",
    "        h = np.zeros((hidden_size, 1))\n",
    "        c = np.zeros((hidden_size, 1))\n",
    "\n",
    "        # Forward pass\n",
    "        z_s, f_s, i_s, g_s, C_s, o_s, h_s, v_s, outputs = forward(inputs_one_hot, h, c, params)\n",
    "        \n",
    "        # Backward pass\n",
    "        loss, _ = backward(z_s, f_s, i_s, g_s, C_s, o_s, h_s, v_s, outputs, targets_one_hot, params)\n",
    "        \n",
    "        # Update loss\n",
    "        epoch_validation_loss += loss\n",
    "    \n",
    "    # For each sentence in training set\n",
    "    for inputs, targets in training_set:\n",
    "        \n",
    "        # One-hot encode input and target sequence\n",
    "        inputs_one_hot = one_hot_encode_sequence(inputs, vocab_size)\n",
    "        targets_one_hot = one_hot_encode_sequence(targets, vocab_size)\n",
    "\n",
    "        # Initialize hidden state and cell state as zeros\n",
    "        h = np.zeros((hidden_size, 1))\n",
    "        c = np.zeros((hidden_size, 1))\n",
    "\n",
    "        # Forward pass\n",
    "        z_s, f_s, i_s, g_s, C_s, o_s, h_s, v_s, outputs = forward(inputs_one_hot, h, c, params)\n",
    "        \n",
    "        # Backward pass\n",
    "        loss, grads = backward(z_s, f_s, i_s, g_s, C_s, o_s, h_s, v_s, outputs, targets_one_hot, params)\n",
    "        \n",
    "        # Update parameters\n",
    "        params = update_parameters(params, grads, lr=1e-1)\n",
    "        \n",
    "        # Update loss\n",
    "        epoch_training_loss += loss\n",
    "                \n",
    "    # Save loss for plot\n",
    "    training_loss.append(epoch_training_loss/len(training_set))\n",
    "    validation_loss.append(epoch_validation_loss/len(validation_set))\n",
    "\n",
    "    # Print loss every 5 epochs\n",
    "    if i % 5 == 0:\n",
    "        print(f'Epoch {i}, training loss: {training_loss[-1]}, validation loss: {validation_loss[-1]}')\n",
    "\n",
    "\n",
    "    \n",
    "# Get first sentence in test set\n",
    "inputs, targets = test_set[1]\n",
    "\n",
    "# One-hot encode input and target sequence\n",
    "inputs_one_hot = one_hot_encode_sequence(inputs, vocab_size)\n",
    "targets_one_hot = one_hot_encode_sequence(targets, vocab_size)\n",
    "\n",
    "# Initialize hidden state as zeros\n",
    "h = np.zeros((hidden_size, 1))\n",
    "c = np.zeros((hidden_size, 1))\n",
    "\n",
    "# Forward pass\n",
    "z_s, f_s, i_s, g_s, C_s, o_s, h_s, v_s, outputs = forward(inputs_one_hot, h, c, params)\n",
    "\n",
    "# Print example\n",
    "print('Input sentence:')\n",
    "print(inputs)\n",
    "\n",
    "print('\\nTarget sequence:')\n",
    "print(targets)\n",
    "\n",
    "print('\\nPredicted sequence:')\n",
    "print([idx_to_word[np.argmax(output)] for output in outputs])\n",
    "\n",
    "# Plot training and validation loss\n",
    "epoch = np.arange(len(training_loss))\n",
    "plt.figure()\n",
    "plt.plot(epoch, training_loss, 'r', label='Training loss',)\n",
    "plt.plot(epoch, validation_loss, 'b', label='Validation loss')\n",
    "plt.legend()\n",
    "plt.xlabel('Epoch'), plt.ylabel('NLL')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3、LSTM 的 PyTorch 实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Net(\n",
      "  (lstm): LSTM(4, 50)\n",
      "  (l_out): Linear(in_features=50, out_features=4, bias=False)\n",
      ")\n"
     ]
    }
   ],
   "source": [
    "import torch\n",
    "import torch.nn as nn\n",
    "import torch.nn.functional as F\n",
    "\n",
    "class Net(nn.Module):\n",
    "    def __init__(self):\n",
    "        super(Net, self).__init__()\n",
    "        \n",
    "        # Recurrent layer\n",
    "        self.lstm = nn.LSTM(input_size=vocab_size,\n",
    "                         hidden_size=50,\n",
    "                         num_layers=1,\n",
    "                         bidirectional=False)\n",
    "        \n",
    "        # Output layer\n",
    "        self.l_out = nn.Linear(in_features=50,\n",
    "                            out_features=vocab_size,\n",
    "                            bias=False)\n",
    "        \n",
    "    def forward(self, x):\n",
    "        # RNN returns output and last hidden state\n",
    "        x, (h, c) = self.lstm(x)\n",
    "        \n",
    "        # Flatten output for feed-forward layer\n",
    "        x = x.view(-1, self.lstm.hidden_size)\n",
    "        \n",
    "        # Output layer\n",
    "        x = self.l_out(x)\n",
    "        \n",
    "        return x\n",
    "\n",
    "net = Net()\n",
    "print(net)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epoch 0, training loss: 1.3143028438091278, validation loss: 1.3969730734825134\n",
      "Epoch 5, training loss: 0.75217468701303, validation loss: 0.8081622838973999\n",
      "Epoch 10, training loss: 0.552385289594531, validation loss: 0.5987649708986282\n",
      "Epoch 15, training loss: 0.4532728582620621, validation loss: 0.48800831139087675\n",
      "Epoch 20, training loss: 0.4020617565140128, validation loss: 0.43309240639209745\n",
      "Epoch 25, training loss: 0.3719896202906966, validation loss: 0.3970140278339386\n",
      "Epoch 30, training loss: 0.35203106738626955, validation loss: 0.373447123169899\n",
      "Epoch 35, training loss: 0.33728282172232865, validation loss: 0.3550317347049713\n",
      "Epoch 40, training loss: 0.32612757533788683, validation loss: 0.34074000269174576\n",
      "Epoch 45, training loss: 0.317566717416048, validation loss: 0.3295662462711334\n",
      "\n",
      "Input sequence:\n",
      "['a', 'a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b']\n",
      "\n",
      "Target sequence:\n",
      "['a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'EOS']\n",
      "\n",
      "Predicted sequence:\n",
      "['a', 'a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'EOS']\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX8AAAECCAYAAAAW+Nd4AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nO3deXRU9d3H8fcvEEjYAiQgsgbEYlgLBllEi6ACYuuKKIqiVdC2Wmu1aj0+5anViktrXeqKtXXp01qXIoobSC0ICohSWZQtlIBsgUAIe/J7/vjOZJ1AAplMMvfzOueeuXPnzsz3ksP3/ua3Ou89IiISLAmxDkBERGqekr+ISAAp+YuIBJCSv4hIACn5i4gEUP1YB1AZaWlpPj09PdZhiIjUKYsWLdrmvW8V6bU6kfzT09NZuHBhrMMQEalTnHPrKnpN1T4iIgGk5C8iEkBK/iIiAVQn6vxFpGYcPHiQ7Oxs9u3bF+tQpAqSkpJo3749iYmJlX6Pkr+IFMnOzqZp06akp6fjnIt1OFIJ3ntycnLIzs6mc+fOlX5fVKp9nHOJzrm3KnHeLc65D6MRg4hU3b59+0hNTVXir0Occ6Smplb511q1l/ydc8nAp8B3jnBeJ+AqYGt1xyAiR0+Jv+45mr9ZtZf8vfd7vfe9gewjnPoH4M7q/v6SvvoK7rgDdu2K5reIiNQ9Ment45wbB3wJLDvMOROdcwudcwu3bj26Hwdr18KUKbCswm8Rkdrk0UcfZciQISQnJzNkyBBef/31Kr1/8eLFPP/880c8b9OmTdx3331HG2ZEQ4cOrdbPizYXrcVcnHOrvPddK3jtFaAjVu3UDbjbe/94RZ+VmZnpj2aE76pVcOKJMHUqXHNNld8uEjjLly8nIyMj1mHQtWtXVq1aFeswqmTo0KHMnj07Zt8f6W/nnFvkvc+MdH5Mevt478cBOOfSgecOl/iPRefO0LAhLF8ejU8XiXM33wxffFG9n/nd78Ijj1TpLVlZWdx1110kJydTWFjI888/z9KlS5kwYQIJCQlMmDCBG264AYDZs2cze/ZsJk+eDFhCHj16NK+++ipt2rRh2rRpRZ85efJkXnjhBQAmTJjACSecwDvvvINzjlmzZrFz504uuugi9u/fT48ePTj11FO57rrrKhXz9u3bufLKK8nJyWHAgAE88sgjbN26lUsuuYS9e/fSt29fnnzyyYjHakrUq32cc52dcw9F+3siqVcPunVTtY9IXffWW29x7bXXFlXpbNiwgalTpzJ9+vQjVvMkJSXx2WefkZeXx8aNGys8Lzc3l3nz5tGtWzc+//xzPvnkE0aNGsWbb75JTk5OpRM/wH333cfYsWOZN28eO3bs4L333uPjjz+mZ8+ezJ8/n1NPPZXCwsKIx2pK1Er+4Sof7/1a4NYKzskCzoxWDADdu8P8+dH8BpE4VcUSejSdffbZDBw4sOh5vXr1+OUvf0laWhqHDh067HuvvvpqADp16sSBAwcqfd4JJ5zAPffcw4wZM4p+SVTWsmXLuP766wEYNGgQy5YtY9KkScyePZtzzz2X/v37k5CQwKhRo8odqylxP71D9+6wbh3k58c6EhE5Wk2aNCn1fPLkyTz99NPcf//9FBQUVOm9lT3vzTffZOrUqcyZM4czz6xaGbVHjx7MD5U658+fT48ePZg7dy6XXXYZ06dP5/3332f16tURj9WUuB/hm5EB3sPXX0O/frGORkSqw4UXXsiIESPo0qULhw4dYt++fSQlJVXrd5x88smcd955dOnShfbt2zNlyhTatWtXqffeeeedjB8/nieeeIIBAwZw9tlnk5WVxRVXXMH+/ftp3749nTp1ol69euWO1ZSo9fapTkfb2wesvr9HD3jpJbj88moOTCTO1JbePrXB5MmT+eijj2jQoAFJSUncf//99OjRI9ZhVahO9PapSV27WsOvGn1FpComT55c5br+uiTu6/wbNLC+/uruKSJSLO6TP1i9v0r+IiLFApH8u3e30b6H6eUlIhIogUn+BQWwcmWsIxERqR0CkfzDDeCq+hGp3YYPH87ixYsBmDlzJmPGjDns+ZEmU7vxxhsjnjthwgSysrIq/KzwVA8lVXaiuMrKyspiwoQJ1fZ5xyK+k/8338ADD9Dt+F04p0Zfkdpu5MiRzJw5E4APP/yQESNGVPkzHnvssaP67kjJv2/fvlwTp7NCxnfyX7oUbr+dRhtWkp6ukr9IVdx8MwwdWr3bzTcf/jtHjBjBhx/a4n4zZ85kxIgR5OfnM2rUKAYNGlQ0BcPhlPw1sG7dOgYPHszw4cNZsWIFAEuXLqV///4MGDCAJ598kp07dzJkyBAWL17MkCFDmDJlStH7S04SB/D5558zePBg+vfvz8svv1z0fQ8++CCnnHIKP/jBD44YX0lr167ljDPO4JRTTuHBBx8E4Ouvv+bUU0+lf//+3HvvvRUeO1bxnfzT0+0xK4vu3ZX8RWq73r17s3r1ajZt2sS+ffvo0KEDGzZs4IYbbuCjjz5izZo1bN68udKfN2XKFG677TbeffddcnNzgfKTwqWkpDBnzhz69u3LnDlzuP322yv8vB//+Me89NJLzJkzhwceeKDoMys7eVxZt912G7/+9a+ZP38+M2bMYPny5UyfPp0LL7yQBQsW0LFjR4CIx45VfA/yCi9mvHYt3bvDhx/CoUNQP76vWqRaxGpetyFDhnDvvfcWzaeTlJTEiy++yIsvvkhubi579+6t9GetWbOGPn36kJiYSN++fYGqTQpXVk5ODl26dAEgIyODtWvXApWfPK6s5cuXM2jQIBISEjjllFNYsWIF48eP54477uDcc89l9OjRABGPHav4Lvk3b27b2rVkZMD+/ba6l4jUXiNHjuSpp55i5MiRADz77LOcf/75vPLKKzRu3LhKn9WxY0e++uorDh06xJIlS4CKJ4VLTk4mPz+fw015k5aWRlZWFgcOHGDFihV0DhUwKzt5XFndu3dn/vz5eO9ZsGABGRkZzJo1izvuuINp06YxZcoUDh48GPHYsYr/MnB6ulX7XGlPly+3Eb8iUjudddZZNGzYkNNPP73o+fXXX8/TTz+Nc46NGzeSHq7SPYJf/OIXXH755Tz88MNFE79VNCncxIkTGTZsGM2aNeODDz6I+HmPPfYY48aN4+DBg9x22200b978mK71gQce4JprriE/P58xY8Zw0kknsXv3bsaPH8+hQ4cYOXIkiYmJdO3atdyxYxX3E7tx4YWwYgU75y2jeXP47W9tUXcRKU8Tu9VdVZ3YLb6rfcDq/bOySGnmaddOjb4iIhCE5J+eDnv3wpYtZGSor7/IkdSF2gAp7Wj+ZvGf/Mv0+Fm+HGpwmUyROiUpKYmcnBzdAOoQ7z05OTlVXswm/ht8SyX/geTnQ3Y2VFNXWZG40r59e7Kzs9m6dWusQ5EqSEpKon379lV6T/wn//CyaFlZZJxqu8uWKfmLRJKYmFjUfVHiW/xX+zRpAq1aFVX7gOr9RUTiP/mDVf2sXUtaGqSlqcePiEgwkn9ooBegOX5ERAhK8u/cGdatg4KCoh4/6swgIkEWnOR/8CBs3EhGBuzYAVWYGFBEJO4EJ/lD0dTOoEZfEQm2YCT/8CRQodk9QfX+IhJsUUn+zrlE59xbRzjnz865+c65ac656I436NQJnIO1a2nbFpo1U/IXkWCr9uTvnEsGFgFnHeacIUB97/1AoBlwdnXHUUrDhtC2LWRl4Rya40dEAq/ak7/3fq/3vjeQfZjTNgN/iFYMEaWnF63kou6eIhJ0Manz996v9N5/5py7ACgE3i97jnNuonNuoXNuYbXMMxIa6AWW/Ddvhu3bj/1jRUTqopg1+DrnfgDcBHzfe19uIU3v/TPe+0zvfWarVq2O/Qs7d7YZ3Q4eLGr0VdWPiARVTJK/c64NcBtwrvc+r0a+ND3d5nJev76ou+fSpTXyzSIitU7Uk79zrrNz7qEyh68Cjgfec87Ncc5dE+04Sk7t3KkTNG4MX30V9W8VEamVotbF0nvfNfS4Fri1zGtTgCnR+u6ISiT/hOHQsyf85z81GoGISK0RjEFeAO3bQ716RRO8hZO/5vgRkSAKTvKvXx86dCjq8dOrF+TkaI4fEQmm4CR/KNXds1cvO6SqHxEJomAl/xLz+vfsaYfU6CsiQRSs5N+5M3z7LezdS+vW0Lq1Sv4iEkzBS/5gC7tgVT9K/iISRMFK/uGpnUNVP7162UCvwsKYRSQiEhPBSv4l+vqD1fvv3Qtr1sQwJhGRGAhW8j/+eJveWT1+RCTggpX8ExJsYZdQtU+PHnZYPX5EJGiClfyh1Lz+jRtDly4q+YtI8AQv+ZcY6AXq8SMiwRTM5J+TA3k2k3SvXrByJezbF+O4RERqUPCSf4TungUFsGJFzCISEalxwUv+Ebp7gqp+RCRYgpv8QyX/E0+EBg2U/EUkWIKX/NPSoFGjopJ/YiJkZKi7p4gES/CSv3PlevxoVS8RCZrgJX+w5B+q9gFr9M3Ohh07YheSiEhNCmbyDw/0Cq3hGJ7mYenS2IUkIlKTgpn8O3eGXbuKivrq8SMiQRPc5A9FVT8dOkBKipK/iARHMJN/eKBXaC5n59ToKyLBEszkf9JJkJQEc+YUHerVy7p7hpoBRETiWjCTf3IyDBsG06cXZfuePSE3FzZsiHFsIiI1IJjJH2D0aFi9Gr75BtDCLiISLMFO/gBvvw0U9/jRSF8RCYLgJv9OnSzjT58OQMuW0LatSv4iEgzBTf5gpf9//xt27gS0sIuIBEdUkr9zLtE599ZhXk9yzk13zn3pnHvROeeiEccRjR4Nhw7BBx8AlvyXL7dDIiLxrNqTv3MuGVgEnHWY064Asr33fYAWRzg3egYNghYtiqp+evWC/fth1aqYRCMiUmOqPfl77/d673sD2Yc5bRjwQWh/FnBGdcdRKfXrw8iRMGMGFBZqmgcRCYxY1fmnAjtD+7uAlmVPcM5NdM4tdM4t3Lp1a/QiGT0atmyBhQvJyICEBFiyJHpfJyJSG8Qq+W8DUkL7KaHnpXjvn/HeZ3rvM1u1ahW9SEaOtIw/fTrJyZCZCW++qZG+IhLfYpX8ZwJnh/aHAR/FKA5ITbW6/1B//2uusb7+CxbELCIRkaiLevJ3znV2zj1U5vDLQDvn3BJgO3YziJ3Ro+Hzz+Hbb7nsMlvl8bnnYhqRiEhURS35e++7hh7Xeu9vLfPafu/9ud773t778d7HuJIlPNr3nXdo1gzGjoW//hV2745pVCIiURPsQV5hvXrZpP6hLp/XXmuJ/+9/j3FcIiJRouQPNqH/6NE22Gv/fgYNgowMVf2ISPxS8g8bPRry8+Hjj3HOSv/z5mldXxGJT0r+YcOG2QIvoaqf8eMhMRGmTo1xXCIiUaDkH9aokd0A3n4bvKdVKzj/fPjLX2zKBxGReKLkX1KZBV6uvRZycuCf/4xxXCIi1UzJv6Rwl8+3bELSM8+0af/V8Csi8UbJv6ROnaBfP3jpJfCehAQb8fvBB7B2bayDExGpPkr+ZU2cCF9+CZ9+CsDVV1tP0D/9KcZxiYhUIyX/ssaNgyZN4KmnABv7NXIkPP88FBTEODYRkWqi5F9W06ZwxRXwt7/Bjh2ANfxu2ADvvRfj2EREqomSfyTXXw/79lk/T+Dcc6F1a3jyyRjHJSJSTZT8I+nTBwYOtKof72nQAG66ycZ/vfturIMTETl2Sv4VmTQJVqyAjz8G4NZboVs3+NGPYM+eGMcmInKMlPwrcskl0Lx5UcNvw4bw9NPW5fOee2Icm4jIMVLyr0ijRnDVVfDaa7bGL/C971nXz4ce0iLvIlK3HVXyd879qLoDqZUmTYKDB+GFF4oOPfig/SCYNAkKC2MXmojIsTjakv+E6gyi1srIsOL+008XZfrUVHj4YZvu+dlnYxyfiMhRUrXPkUyaBGvWwIcfFh0aPx7OOANuvx02bYphbCIiR6n+4V50zo2LdBhoGZ1waqELL4S0NGv4PftswKZ7eOopW/3xllvglVdiHKOISBUdqeR/YoStK/BilOOqPRo2tNndpk2DjRuLDn/nO3DXXbbQu0b+ikhd47z3VX+Tcz/y3v8xCvFElJmZ6RcuXFhTX1fe6tXQtSv8+tdw991Fh/fvt/Fg+/fD4sXWECwiUls45xZ57zMjvaYG38o44QQYMQIefRS2bSs63LChzfa5YYPNB6eJ30SkrlCDb2U9+CDk5tpQ3xIGDYLHH4cZM6waSESkLlCDb2X16gW/+AXcd5919xk+vOiliRPhiy9gyhSrBrrsshjGKSJSCYet83fO/QoIn+BK7OO9/3V0QysW8zr/sL17oXdv8N6G+CYnF7104ACcdRZ89hnMmQMnnxzDOEVEOPY6f0dx4j8DmAwMra7g6pTkZBvwtXp1uQl+GjSAV1+FVq3g/PNh8+YYxSgiUgmHTf7e+/8FfgusB0YD/wX6ee+H1UBstdOwYTBhgrUBLFlS6qXWreHNNyEnBy6+2H4NiIjURodN/s65e7HEfzkwBXgaaOScG3yY9yQ556Y75750zr3onHMRzmnsnPunc26uc+6BY7yGmvfQQ9avc+LEcl18+vWzJR/nzLE1AEREaqMjVfu0Bd7BSvzfB64Lbdce5j1XANne+z5AC+CsCOdcDsz33p8K9HDOZVQ18JhKTYVHHrFF3iMs73XppXDHHVZD9LvfxSA+EZEjOGxvH+/91UfxmcOA10L7s7B2gvfLnJMLdHLO1QOSgbpXQTJuHLz4Itx5J5x3nq30XsJvfgMrV8LPfw7t2sHYsTGKU0Qkgmj0808Fdob2dxG5W+gbwEhgNbDce7+67AnOuYnOuYXOuYVbt26NQpjHyDkr9RcUwE9+Yj2ASqhXD156CU47Da68EmbPjk2YIiKRRCP5bwNSQvspoedl3Qk86b1PB1pGakPw3j/jvc/03me2atUqCmFWg86drYg/bZq1A5SRlGQNwCecYD2AtACMiNQW0Uj+M4GzQ/vDgI8inNMU2Bfa3w80iUIcNeNnP7M6ndtvtxXey2jZ0hZ9b9wYRo2C9etjEKOISBnRSP4vA+2cc0uA7cBq51zZYvETwA3OuXlYnf/MKMRRM5yz7j39+tnQ3qVLy53SsaNN/5CXZzeA3NwYxCkiUsJRzepZ02rNCN/D2bABMjNt7d9PP7U1AMqYNQtGjoTBg20a6IYNYxCniARGNGb1lLLatbMK/g0bKhzhNWyYLQf8r3/ZAmF14L4rInFKyb86DRgAU6dadr/ppojZfdw4+J//gT//OeIQARGRGqHkX90uv7x4hNcfI69386tfwejR8NOfwty5NRyfiAhK/tFx773w/e9bdo+wxmNCgo0BSE+3GqISq0OKiNQIJf9oSEiAl1+2NQAuvtgm+y+jeXN44w3rATRmjCaBE5GapeQfLU2bwttvQ4sWcM458N//ljulZ0/rJfrJJ3DzzTGIUUQCS8k/mtq2tQ7+e/bYDSBCB/9LLrEFwp580m4EIiI1Qck/2nr0gNdfh2++gQsvhP37y51y771w5plwww2wYEEMYhSRwFHyrwnDhlmx/qOP4Ic/LNcFtH59+L//gzZt4Oqr4dChGMUpIoGh5F9TrrjCivgvvwx3313u5dRU+P3vbXaI556LQXwiEihK/jXpzjvhuuvsJhChgv+CC+D0020Q2M6dEd4vIlJNlPxrknM28Ouss6yCf/78ci//7newbZvdH0REokXJv6aFK/jbt7cG4G+/LfXyySfb4i9/+AOsWROjGEUk7in5x0LLljYJ3M6dcNFF5XoA3Xef3SNuvz1G8YlI3FPyj5VevWx2t3nzbBK4Etq2tcT/j3/Av/8do/hEJK4p+cfSxRdbI/Azz9hEcCXceqvVDP3sZ1BYGKP4RCRuKfnH2j332PJeN94Ic+YUHW7UCH77W1i0yCaBExGpTlrJqzbIzYVTToFdu2DhQivyYyX+AQNs1s9vvrF1gEVEKksredV2zZtbA3B+vk32Exrim5BgA782boQHH4xxjCISV5T8a4vu3W1o77x5MHly0eEhQ2DsWOsB9NlnsQtPROKLkn9tMnYsXHONZfpZs4oO//GP1gNozBjIyYlhfCISN5T8a5tHH4Vu3WwuoK1bARsW8I9/wKZNdli9f0TkWCn51zaNG9sI4O3bbYrPUIN8ZqaN+n33XfjNb2Ico4jUeUr+tVGfPvDQQ7YS2B/+UHR40iQr+U+eDB98ELvwRKTuU/KvrX78YzjvPFvm6/PPAZv47amnrG143DhYvz7GMYpInaXkX1s5B1OnQuvWcOmlttI7Viv02ms2HdAll2jhdxE5Okr+tVlqqi3+snq1TQEdqv/v1s2WA5g/H37+83ILg4mIHJGSf233ve/B//6v3QTuuafo8MUX27w/jz9ui8Bs2RLDGEWkzlHyrwvuuguuugp+9Sv405+KDj/0EDz8sPUA6tkT/vnPGMYoInVKtSd/51ySc266c+5L59yLzjlXwXm/cM7Nd87NcM41qO444opz8OyztgLYddfBe+8BNv3DLbfYdEDt2sH559sYsV27YhyviNR60Sj5XwFke+/7AC2As8qe4JzrAvTw3g8EZgDtoxBHfElMtJFePXtanc/ixUUv9ewJn35qPxD+/Gfo3Rv+9a8YxioitV40kv8wINwLfRZwRoRzhgMtnHMfA6cBa8ue4Jyb6Jxb6JxbuDU00jXwmjWDd96BFi3gnHNg3bqilxo0sMFfc+bYfeKMM+Cxx2IYq4jUatFI/qnAztD+LqBlhHNaAVu996djpf4hZU/w3j/jvc/03me2atUqCmHWUW3bwowZsHevrQOwY0eplwcNgi++sCECN91kNwT1BhKRsqKR/LcBKaH9lNDzsnYBX4f21wDtohBH/OrRw6aAXr3asvyePaVebtwYXn0Vxo+Hu++2cWK6AYhISdFI/jOBs0P7w4CPIpyzCAgvMNAVuwFIVQwdCn/5C8yda78AQoPAwurXhxdesIHCDz0EEydCQUFMIhWRWigayf9loJ1zbgmwHVjtnHuo5Ane+3lAjnNuAfC1914z1R+NsWNtjce5c2HECNi5s9TLCQlW73/XXbZUwLhxGhEsIqZ+dX+g934/cG6Zw7dGOO+G6v7uQLrsMmvtvfRS6wr63nvWIBzinNX7p6RY9U9ennUaatQohjGLSMxpkFc8uOgieP11+PJLGDYMtpVvZrntNnj6aRsQNniwrQksIsGl5B8vvv99G+K7YoX189y8udwpEyfCW2/ZbKAnnwx//WsM4hSRWkHJP56MHAnTp1svoKFDS40DCBs92rqC9uljbQCTJlmvUREJFiX/eDN8uNXtfPst9OtXNBVESR06wEcfwR13wDPPwMCB8PXXET5LROKWkn88Ov10WLDAJvwZNcpafMss/JuYCL/9rQ0Y3rDBqoGef17jAUSCQsk/Xp14IsybZ72B7r7bBoPl5pY7bdQoqwY6+WT44Q/tvvGf/8QgXhGpUUr+8axxYxsH8NhjVhWUmQlLlpQ7rX17qwZ67jlYtgz69rVFYsqMGxOROKLkH++cg5/8xKb53LPHKviffrpc/U5CgpX8v/4arr4afvc7OOkkmyZCVUEi8UfJPygGD7aF4AcPhuuvt4bh1avLnZaWZksHzJtnywdfcgmceaZNGS0i8UPJP0jatIEPPrCS/8KF0KsXPPJIxEl/Bg60NuNHH7WxYwMHwrnn2v1DROo+Jf+gcc5Gey1bZoPBfvYzOO00WL683Kn168ONN8LatdZhaO5caxi+8EI1CovUdUr+QdW+vQ0Ie/FFq+j/7ndtofj8/HKnNm1qk8NlZdkywjNn2iCxsWNh0aKaD11Ejp2Sf5A5B1dcYb8Czj8fJk+G73zH1oIsMy4AbHK4yZPtl8Cdd9oYgcxM+N73bHkBTRktUnco+Qscdxz87W/w8cc2MGzCBMvqH0VaigFatoR774XsbHj4YZtF4oILoFs3ePxx2L27ZsMXkapT8pdip50G8+fDyy9DTo7NEPqDH9hkcRGkpMAtt8CqVfD3v1vvoBtvtOkjfvpTtQuI1GZK/lJaQoLN+LZihc3/MHu2LRs5bhwsXRrxLfXrw5gx8Mkn1kV05Eh46ino3dt6CU2dql8DIrWNkr9ElpxsM7+tWmXDfadNg549be2AxYsrfNvAgTZV9IYN8Pvf2yjha6+F44+3TkaffKJBYyK1gZK/HF7r1vDAA1axf/fd1tWnXz/r9D9/foVvS0uDm2+Gr76yLqJjxlht0qmnQpcu8Mtf2msiEhvO14FiWGZmpl+4cGGswxCwyeGeeMKK9Tk5VtS/8Ua4+GJbTvIw8vKsV9Arr9hYs4IC+zExbpx1G+3SpYauQSQgnHOLvPeZEV9T8pejsnu3zQH9+OOwcqWNHp40ybbjjz/i27dssXmDXnnFqoLAxg5ccIFtvXpZT1QROXpK/hI9hYXw/vs2c+g779hCAWPGwHXX2fzQCUeuWczKgtdegzfeKG4T6NLFbgLnn28/LurXj/6liMQbJX+pGStXWpXQn/4Eu3ZB5842ZuDKKyE9vVIfsWmTtS2/8YY1Lxw8CM2bw4gRcM459njccVG9CpG4oeQvNWvPHnj9dbsJzJplx4YNs7miL7jA1hmohJ07bRXKGTNsC69Jn5lpi9Cceab9KjhCU4NIYCn5S+ysW2fTRbzwgs0LkZxsq8hfcokV5St5IygstBXH3nnHbgTz59uxRo2sdmn4cLsZ9O5dqZomkUBQ8pfYKyyEOXNsGol//MNafBs1Kn0jaNSo0h+3Y4eNP5s507bwIOS0NLsZhLfevaFevehckkhtp+QvtUtBAfz73zYnxGuv2Y0gKcmqhkaPtq1Tpyp95IYNVsM0c6ZNUbR2rR1v1gyGDLEbwZAhNiV1UlIUrkmkFlLyl9qroMCy9bRp8NZbxauL9eplN4FzzrGK/cTEKn3s+vV2f/n4Y9vCyxUkJtoYtcGDi7e2bav5mkRqCSV/qRu8h2++sXUGpk+3aqJDh6xdIFyxP3z4UVXsb9li8w7Nm2fdSRcsgH377LWOHWHAgOKtX78q1UCJ1Fo1mvydc0nAP4AOwBLgSl/BlzjnbgHO8d6febjPVCHYrMwAAAuYSURBVPIPqNzc4rqcmTNt0RmA1FRbhey006wup3fvKg8EOHDAGpDnzrX1iefPt7ZpsDaCPn3sRnDyybb16FHlHx8iMVfTyf9aINN7f71zbjrwqPf+/QjndQKmAVuV/KVSSlbsz5pldTsATZrAoEE2cdCQIdC/v1X2V9HmzXYjCG8LFthwBYCGDe2GEL4Z9O4N3btXurOSSEzUdPJ/BXjNe/9aqGTfynt/Z4Tz3gSeAW5R8pej8t//WtF9zhx7XLLEqo6cg5NOglNOKd56967ygIDCQmuCWLjQlqtctMgWsA/fEJyzkci9etnWsydkZMCJJ6pRWWqHwyX/aAyaTwV2hvZ3Ad0iBDQO+BJYVtGHOOcmAhMBOnbsWP1RSt3XsaNtl11mz3futPqbzz6zbcYMG2MAlvh79YK+fYu33r0PW3RPSLBEfuKJxV9RWAhr1thCNeHtq6+svTq88qVz1lmpW7fiLfw5HTqo66nUDtEo+b8MvB4q+f8caOm9v6vMOa8AHbGbTzfgbu/94xV9pkr+clS8t18HCxZYPc7nn9taBDt22OsJCbZm8Xe/azeCcBG+Y8cqzyq3b5/1KFqxwtqsv/66eMvPLz6vYUP7tRC+GZx4Ipxwgm0dOmgOI6leNV3tcw0wwHs/yTn3NvB77/2HFZybDjynah+pMeEbwuLFxduSJcWtvWDtBT172o0gI6N4a9++yjcF72HjRrshrFxZelu9GvbvLz63fn2bDil8M+jSxbbOne2xadNq+jeQwKjp5N8QeA0r2X8J/A/wY+/9rRHOTUfJX2qDXbus/qZkfc5//lP8KwEs+550UnHFfnjr2vWoGpgLCyE7224C4W3VquL9cNtCWFqa3Qg6d7Z58tLTi/c7dbKZM0RKUj9/kaPhPWzdCsuWWZ1OyW3DhtLntm5tN4Jwcb1kkf3446s8LsF7u++sWWOjldesKd7PyrIfKgcOlA+hUyertSr72KGD3Ty0RkKwKPmLVLf8fCuer1xpxfVwXc6aNXZjKPn/qmFDy8LhInq42B5+3qZNlVuBCwvh22/tRpCVZTeF//7Xbgrr1tn+3r2l35OUZDVXHToUb+3a2bHwY1qaJsaLJ0r+IjVp/37LwOEie7i4Hi6yb9lS+vz69S37hnsvhYvqHTpYRm7f3ga2VaHY7j1s21Z8I1i/vvSWnW1tEQUFpd+XmGihtG1b/FhyO/5421JS9CuiLlDyF6lN8vMtI4dvBuvX2/Pwlp1t01qUFC62h4vpJTN0eL9NG/uVUUkFBTawLTvbfqyUfNy4sXjLyyv/3qSk4htBmzb2eNxxtt+mTfH+ccdVKSSpZkr+InVJQYEtaZadXX5bv94y8oYN5Sv9AVq2LM7KJbNzyWx83HF2XiXrd/LyrIppwwZ7jLRt3ly6bbyklBRrjzjuuNKPrVtDq1bFj61aWVgaB1F9lPxF4o33kJNTfCMom5k3bSrej3STqF+/OANH2sLZOC3NHps2PWI9z/79dhPYvNm+ftMm29+ypfxjTk7kz0hIsBtAya8OP6am2paWVnpfVVAVq+kRviISbc5Z5ktLswFqFfHeJsgrmZVL7m/datl45Up7LDkiraQGDYozcTjrltxPTaVhaiodW7akY2oqnJhq3V8r+HVx8KDdALZssRDCYWzdam0V27bZ/tdf28wd27aVb58Iq1cPWrSwm0ZqaunH8PGyj82b236QJ+tT8heJZ85ZlmvRwsYoHEl+fnE2jrTl5Fgm/uIL29++vXTPppLCxfgIGTixZUvaNG9Om3Bsx7eAjFBGbt7cJusrceMoLLRxD9u2FYcQfty+3bZwON9+a0M2tm+P3F5RUuPGxV8Zfoy0paQUP5bcr8vrRyv5i0ixxo1tS0+v3PkFBVbZH868OTml97dvt9fDz1eutP3c3IpvGmCJv0SmTWjenOYpKTRPSaFr+Hh4a59ivzKaNbPn4f2mTTlYkEBubukwduwo3nJzSz9fv97G9uXm2lRRR6oVT0qK/NUpKVZTViKUoseSW5MmxY81PbWHkr+IHL169YqrgKoiXJQvm3137LCsG86+ubnF29q1xcd27TpyZgYSmzShVdOmtKoo+zZtCp2bQu8ymbhJEwobN2UXzcgtaMrOQ43ZeSCZ3Lx67NxJqW3XruLHXbusd+/OnfarIy+vfMetiiQllfr6ou2yy+Dqq6v2z1sZSv4iUvMSEorrVCr7K6OkwkLYvbt01g1vJY/l5ZV/zMoqzsx5eaUnWCoZItA8tBVJSrKM3Lhx8WPjxrb0W5PGcFzjUsd8ciP2NWhGXkIKu2hKHs3IK2hEXmFj8g4lk3cwybb9ieQfSGT3nnrsznfs3m2Xl5cHe/ZU/Z+nMpT8RaTuSUgorlM5VgcPFmfacNYtueXlWVvI7t2lH8PH9+yxhob8/NLbgQM4IDm0ta7sdSUnl972TwJuOfbrLEPJX0SCLTGxuFG8Oh06ZHNshG8Qe/bY/t69th9+DG9795bf9uyxgRFRoOQvIhIN9esXtyvUQprCSUQkgJT8RUQCSMlfRCSAlPxFRAJIyV9EJICU/EVEAkjJX0QkgJT8RUQCqE4s5uKc2wqsO8q3pwHbqjGcuiSo167rDhZdd8U6ee9bRXqhTiT/Y+GcW1jRSjbxLqjXrusOFl330VG1j4hIACn5i4gEUBCS/zOxDiCGgnrtuu5g0XUfhbiv8xcRkfKCUPIXEZEylPxFRAIobpO/cy7JOTfdOfelc+5F55yLdUzR5pxLdM69FdoPzPU75/7snJvvnJvmnGsShOt2ztV3zr3qnJvrnHs+SH9vAOfcLc65D51zac65fzvn/uOcuz/WcUWLc66/cy7bOTcntPU51r933CZ/4Aog23vfB2gBnBXjeKLKOZcMLKL4OgNx/c65IUB97/1AoBlwDQG4buB84Evv/anA8cBPCMZ145zrBFwVenoz8DbQBxjlnPtOzAKLrhbAk977Id77IUB/jvHvHc/JfxjwQWh/FnBGDGOJOu/9Xu99byA7dCgo178Z+ENoPwGYTDCu+13gd865+kBzoB/BuG6wv/edof1hwAfe+0LgX8TvdbcALnLOfeacew0YzjH+veM5+acCO0P7u4CWMYwlFgJx/d77ld77z5xzFwCFwGKCcd27vfd7gLnYDTAQf2/n3DjgS2BZ6FAgrhtYBdztvT8F+6V3Icd43fGc/LcBKaH9FII390dgrt859wPgJuD7wCYCcN3OuVTnXENgMFYq7EkArhs4Fyv1/h9wMja/TRCuOwv4sMR+Icd43fGc/GcCZ4f2hwEfxTCWWAjE9Tvn2gC3Aed67/MIyHUDPwfGeO8LgD3AvQTgur3340J13pdibVxPAGc75xKA7xGn1w3cAlwaus6e2N//mP7e8Zz8XwbaOeeWANuxpBAkQbn+q7Cfwe855+YAiQTjup8ArnHOzQNygKkE47rLehQ4B1gCvO29XxXjeKLlceBq4FPgDarh760RviIiARTPJX8REamAkr+ISAAp+YuIBJCSv4hIACn5i5ThnJvgnFtXYh6VUcf4WROqMTyRalE/1gGI1FLPeu9/E+sgRKJFyV/kCJxzk4FTsJGUG4DLsP87LwAdgXXABOyX9AtAJ2ArMDb0Eb2cc/8CWgMXe++X1ljwIhVQtY9IZD90zs12zs0G2gGfhGbQzAHOA64DloWOrcQG4EzEZtocBEwDeoc+axA26+L9ofeKxJySv0hkU733Q733Q7HS/oLQ8S+AzkB3YF7o2LzQ85OAz0LHngcWhvZf8d4fwH4hNIh+6CJHpuQvUjkDQo/9gNXAUmBg6NjA0PMVJc67C/s1ALC7hmIUqTTV+YtEdp1zbmRovxfwr9DcQdnAW4Tq/J1zc7ES/X1APeDPofO2AA9iE5CJ1Dqa20fkCEINvrO997NjHIpItVHyFxEJINX5i4gEkJK/iEgAKfmLiASQkr+ISAAp+YuIBND/A+KJLCOb10Y+AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Hyper-parameters\n",
    "num_epochs = 50\n",
    "\n",
    "# Initialize a new network\n",
    "net = Net()\n",
    "\n",
    "# Define a loss function and optimizer for this problem\n",
    "criterion = nn.CrossEntropyLoss()\n",
    "optimizer = torch.optim.Adam(net.parameters(), lr=3e-4)\n",
    "\n",
    "# Track loss\n",
    "training_loss, validation_loss = [], []\n",
    "\n",
    "# For each epoch\n",
    "for i in range(num_epochs):\n",
    "    \n",
    "    # Track loss\n",
    "    epoch_training_loss = 0\n",
    "    epoch_validation_loss = 0\n",
    "    \n",
    "    net.eval()\n",
    "        \n",
    "    # For each sentence in validation set\n",
    "    for inputs, targets in validation_set:\n",
    "        \n",
    "        # One-hot encode input and target sequence\n",
    "        inputs_one_hot = one_hot_encode_sequence(inputs, vocab_size)\n",
    "        targets_idx = [word_to_idx[word] for word in targets]\n",
    "        \n",
    "        # Convert input to tensor\n",
    "        inputs_one_hot = torch.Tensor(inputs_one_hot)\n",
    "        inputs_one_hot = inputs_one_hot.permute(0, 2, 1)\n",
    "        \n",
    "        # Convert target to tensor\n",
    "        targets_idx = torch.LongTensor(targets_idx)\n",
    "        \n",
    "        # Forward pass\n",
    "        outputs = net.forward(inputs_one_hot)\n",
    "        \n",
    "        # Compute loss\n",
    "        loss = criterion(outputs, targets_idx)\n",
    "        \n",
    "        # Update loss\n",
    "        epoch_validation_loss += loss.detach().numpy()\n",
    "    \n",
    "    net.train()\n",
    "    \n",
    "    # For each sentence in training set\n",
    "    for inputs, targets in training_set:\n",
    "        \n",
    "        # One-hot encode input and target sequence\n",
    "        inputs_one_hot = one_hot_encode_sequence(inputs, vocab_size)\n",
    "        targets_idx = [word_to_idx[word] for word in targets]\n",
    "        \n",
    "        # Convert input to tensor\n",
    "        inputs_one_hot = torch.Tensor(inputs_one_hot)\n",
    "        inputs_one_hot = inputs_one_hot.permute(0, 2, 1)\n",
    "        \n",
    "        # Convert target to tensor\n",
    "        targets_idx = torch.LongTensor(targets_idx)\n",
    "        \n",
    "        # Forward pass\n",
    "        outputs = net.forward(inputs_one_hot)\n",
    "        \n",
    "        # Compute loss\n",
    "        loss = criterion(outputs, targets_idx)\n",
    "        \n",
    "        # Backward pass\n",
    "        optimizer.zero_grad()\n",
    "        loss.backward()\n",
    "        optimizer.step()\n",
    "        \n",
    "        # Update loss\n",
    "        epoch_training_loss += loss.detach().numpy()\n",
    "        \n",
    "    # Save loss for plot\n",
    "    training_loss.append(epoch_training_loss/len(training_set))\n",
    "    validation_loss.append(epoch_validation_loss/len(validation_set))\n",
    "\n",
    "    # Print loss every 5 epochs\n",
    "    if i % 5 == 0:\n",
    "        print(f'Epoch {i}, training loss: {training_loss[-1]}, validation loss: {validation_loss[-1]}')\n",
    "\n",
    "        \n",
    "# Get first sentence in test set\n",
    "inputs, targets = test_set[1]\n",
    "\n",
    "# One-hot encode input and target sequence\n",
    "inputs_one_hot = one_hot_encode_sequence(inputs, vocab_size)\n",
    "targets_idx = [word_to_idx[word] for word in targets]\n",
    "\n",
    "# Convert input to tensor\n",
    "inputs_one_hot = torch.Tensor(inputs_one_hot)\n",
    "inputs_one_hot = inputs_one_hot.permute(0, 2, 1)\n",
    "\n",
    "# Convert target to tensor\n",
    "targets_idx = torch.LongTensor(targets_idx)\n",
    "\n",
    "# Forward pass\n",
    "outputs = net.forward(inputs_one_hot).data.numpy()\n",
    "\n",
    "print('\\nInput sequence:')\n",
    "print(inputs)\n",
    "\n",
    "print('\\nTarget sequence:')\n",
    "print(targets)\n",
    "\n",
    "print('\\nPredicted sequence:')\n",
    "print([idx_to_word[np.argmax(output)] for output in outputs])\n",
    "\n",
    "# Plot training and validation loss\n",
    "epoch = np.arange(len(training_loss))\n",
    "plt.figure()\n",
    "plt.plot(epoch, training_loss, 'r', label='Training loss',)\n",
    "plt.plot(epoch, validation_loss, 'b', label='Validation loss')\n",
    "plt.legend()\n",
    "plt.xlabel('Epoch'), plt.ylabel('NLL')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "nlp",
   "language": "python",
   "name": "nlp"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
